1.Dijkstra代码（50分）

1 #include<bits/stdc++.h>
2 #define INF 0x3f3f3f3f
3 using namespace std;
4
5 int n,a;
6 int mp[85][85];//图 （邻接矩阵）
7 bool vis[85]={0};//访问标记
8 int dis[85];//最短距离
9
10 void Dijkstra(int s){//核心代码
11 //   memset(dis,INF,sizeof(dis));
12     for(int i=1;i<=n;i++){
13         dis[i]=INF;
14     }
15     dis[s]=0;
16     for(int i=1;i<=n;i++){
17         int u=-1,MIN=INF;
18         for(int j=1;j<=n;j++){
19             if(vis[j]==0 && dis[j]<MIN){
20                 u=j;
21                 MIN=dis[j];
22             }
23         }
24         if(u==-1) return;
25         vis[u]=1;
26         for(int v=1;v<=n;v++){
27             if(vis[v]==0 && mp[u][v]!=INF && dis[u]+mp[u][v]<dis[v]){
28                 dis[v]=dis[u]+mp[u][v];
29             }
30         }
31     }
32 }
33
34 int main(){
35     cin>>n;
36     cin>>a;
37     for(int i=1;i<=n;i++){//输入图，注意判断整数和字符
38         for(int j=1;j<=n;j++){
39             int c;
40             if(scanf("%d",&c)==1) mp[i][j]=c;
41             else mp[i][j]=INF;
42         }
43     }
44     Dijkstra(a);//松弛
45     for(int i=1;i<=n;i++){//(1 -> 5) = 9
46         if(i==a) continue;
47         cout<<'(';
48         cout<<a;
49         cout<<" -> ";
50         cout<<i;
51         cout<<") = ";
52         cout<<dis[i]<<endl;
53     }
54     return 0;
55 }

2.Floyd代码（100分）

 1 #include<bits/stdc++.h>
 2 #define INF 0x3f3f3f3f
 3 using namespace std;
 4 
 5 int n,a;
 6 int mp[85][85];
 7 
 8 void Floyd(){//核心代码
 9   for(int k=1;k<=n;k++){
10       for(int i=1;i<=n;i++){            
11           for(int j=1;j<=n;j++){
12               if(mp[i][j]>mp[i][k]+mp[k][j]) mp[i][j]=mp[i][k]+mp[k][j];
13           }
14       }
15   }
16 }
17 
18 int main()
19 {
20   cin>>n>>a;
21   for(int i=1;i<=n;i++){//输入
22       for(int j=1;j<=n;j++){
23           int c;
24           if(scanf("%d",&c)==1)
25               mp[i][j]=c;
26           else
27               mp[i][j]=INF;
28       }
29   }
30   Floyd();
31   for(int i=1;i<=n;i++){//(1 -> 5) = 9
32       if(i==a) continue;
33       cout<<'(';
34       cout<<a;
35       cout<<" -> ";
36       cout<<i;
37       cout<<") = ";
38       cout<<mp[a][i]<<endl;
39   }
40   return 0;
41 }