1 #include<cstdio> 
2 #include<cstring>
3 using namespace std;
4 int n, m; 
5 int f[101][101];
6 intF[101][101]; 
7 int main(){ 
8 scanf("%d%d"，&n，&m);//n的值在1到100之间 
9 memset(f，-1，sizeof(f)); 
10 for(int i = 1; i <= m; i++) { 
11     int u，v，w;//w的值在0到10000之间 
12     scanf("%d%d%d"，&u，&v，&w); 
13     f[u][v]=f[v][u]=w; 
14 }
15 for(int k = 1; k <= n; k++) 
16     for(int i=1;i <=n; i++) 
17         for(int j=1;j<= n; j++) 
18             if(f[i][k]!=-1&&f[k][j]!=-1) 
19                 if(f[i][j]==-1||f[i][j]>f[k][j]+f[i][k]) 
20                     f[i][j]=f[i][k]+f[k][j]; 
21 int ans=2147483647; 
22 for(int i=1;i<=n;i++) 
23     for(int j=1;j<=n; j++){ 
24         for(int x=1;x<=n; x++) 
25             for(int y=1;y<=n; y++) 
26                 F[x][y]=f[x][y]; 
27         F[i][j]=F[j][i]=0; 
28         for(int x=1;x<= n; x++) 
29             for(int y=1;y<=n; y++) 
30                 if(F[x][y]==-1||F[x][y]>F[x][i]+F[i][y]) 
31                     F[x][y]=F[x][i]+F[i][y]; 
32         for(int x=1;x<=n; x++) 
33             for(int y=1;y<=n; y++) 
34                 if(F[x][y]==-1||F[x][y]>F[x][j]+F[j][y]) 
35                     F[x][y]=F[x][j]+F[j][y]; 
36         int res=0; 
37         for(int x=1;x<=n; x++) 
38             for(int y=1;y<x; y++) 
39                 res +=F[x][y]; 
40         ans=min(res，ans); 
41         }
42 printf("%d\n"，ans); 
43 return 0; 
44 }

●判断题

1)(1分)14到16行，将外层到内层的循环变量依次调整为i、j、k，程序的运行的结果不变。(

)

2)这个程序的时间复杂度和m无关。( )

3)20行的ans如果初始化为10^7时，可能无法得到正确结果。( )

4)若将第27到30行的部分和31到34行的两个部分互换，程序的运行的结果不变。( )

●选择题

5)若输入数据为4 5/1 2 3/1 3 6/2 3 4/2 4 7/3 4 2(其中“/”为换行符)，则输出为( )。

A.14

B.18

C.21

D.28

6)这个程序使用了( )算法。

A. Floyd

B. Dijkstra

C. Prim

D. Kruskal

第一空(1分)：_________________

第二空(2分)：_________________

第三空(2分)：_________________

第四空(2分)：_________________

第五空(3分)：_________________

第六空(3分)：_________________