1 #include <stdio.h> 2 int main() 3 { 4     int e[10][10],k,i,j,n,m,t1,t2,t3; 5     int inf=99999999; //用inf(infinity的缩写)存储一个我们认为的正无穷值 6     //读入n和m，n表示顶点个数，m表示边的条数 7     scanf("%d %d",&n,&m); 8      9     //初始化10     for(i=1;i<=n;i++)11         for(j=1;j<=n;j++)12             if(i==j) e[i][j]=0;  13                 else e[i][j]=inf;14 15     //读入边16     for(i=1;i<=m;i++)17     {18         scanf("%d %d %d",&t1,&t2,&t3);19         e[t1][t2]=t3;20     }21     22     //Floyd-Warshall算法核心语句23     for(k=1;k<=n;k++)24         for(i=1;i<=n;i++)25             for(j=1;j<=n;j++)26                 //if(e[i][j]>e[i][k]+e[k][j] ) 27                 if(e[i][k]<inf && e[k][j]<inf && e[i][j]>e[i][k]+e[k][j])                  28                     e[i][j]=e[i][k]+e[k][j];29     30     //输出最终的结果31     for(i=1;i<=n;i++)32     {33          for(j=1;j<=n;j++)34         {35              printf("%10d",e[i][j]);36         }37         printf("\n");38     }39     40     return 0;41 }42 43 /*44 45 4 846 1 2 247 1 3 648 1 4 449 2 3 350 3 1 751 3 4 152 4 1 553 4 3 1254 55 4 956 1 2 257 1 3 658 1 4 459 2 3 360 3 1 761 3 4 162 4 1 563 4 2 164 4 3 1265 66 为测试经过任意数点，加测试数据一组67 */

 1 #include <stdio.h> 2 int e[10][10],k,i,j,n,m,t1,t2,t3; 3  4 void printm() 5 { 6     int i,j; 7     for(i=1;i<=n;i++) 8     { 9          for(j=1;j<=n;j++)10         {11              printf("%5d",e[i][j]);12         }13         printf("\n");14     }15     printf("\n");  16 }17 18 int main()19 {20     int inf=999; //用inf(infinity的缩写)存储一个我们认为的正无穷值21     //读入n和m，n表示顶点个数，m表示边的条数22     scanf("%d %d",&n,&m);23     24     //初始化25     for(i=1;i<=n;i++)26         for(j=1;j<=n;j++)27             if(i==j) e[i][j]=0;  28                 else e[i][j]=inf;29 30     //读入边31     for(i=1;i<=m;i++)32     {33         scanf("%d %d %d",&t1,&t2,&t3);34         e[t1][t2]=t3;35     }36     printf("\n");37     printm();38     39     //Floyd-Warshall算法核心语句40     for(k=1;k<=n;k++)41     {42         for(i=1;i<=n;i++)43             for(j=1;j<=n;j++)44                 //if(e[i][j]>e[i][k]+e[k][j] ) 45                 if(e[i][k]<inf && e[k][j]<inf && e[i][j]>e[i][k]+e[k][j])                  46                     e[i][j]=e[i][k]+e[k][j];47         printm();48     }49    50     return 0;51 }52   53 /*54 55 4 856 1 2 257 1 3 658 1 4 459 2 3 360 3 1 761 3 4 162 4 1 563 4 3 1264 65 */

 1 #include <stdio.h> 2 int main() 3 { 4     int e[10][10],dis[10],book[10],i,j,n,m,t1,t2,t3,u,v,min; 5     int inf=99999999; //用inf(infinity的缩写)存储一个我们认为的正无穷值 6     //读入n和m，n表示顶点个数，m表示边的条数 7     scanf("%d %d",&n,&m); 8      9     //初始化10     for(i=1;i<=n;i++)11         for(j=1;j<=n;j++)12             if(i==j) e[i][j]=0;  13               else e[i][j]=inf;14               15     //读入边16     for(i=1;i<=m;i++)17     {18         scanf("%d %d %d",&t1,&t2,&t3);19         e[t1][t2]=t3;20     }21 22     //初始化dis数组，这里是1号顶点到其余各个顶点的初始路程23     for(i=1;i<=n;i++)24         dis[i]=e[1][i];25 26     //book数组初始化27     for(i=1;i<=n;i++)28         book[i]=0;29     book[1]=1;30     31     //Dijkstra算法核心语句32     for(i=1;i<=n-1;i++)33     {34         //找到离1号顶点最近的顶点35         min=inf;36         for(j=1;j<=n;j++)37         {38             if(book[j]==0 && dis[j]<min) //在集合Q中找到最近的顶点39             {40                 min=dis[j];41                 u=j; //记录下顶点位置42             }43         }44         book[u]=1; //顶点u加入集合P45         for(v=1;v<=n;v++)46         {47             if(e[u][v]<inf) //对每个出边指向点48             {49                 if(dis[v]>dis[u]+e[u][v]) 50                     dis[v]=dis[u]+e[u][v]; //松弛51             }52         }    53     }54     55     //输出最终的结果56     for(i=1;i<=n;i++)57         printf("%d ",dis[i]);58         59     getchar();60     getchar();61     return 0;62 }63 64 /*65 66 6 967 1 2 168 1 3 1269 2 3 970 2 4 371 3 5 572 4 3 473 4 5 1374 4 6 1575 5 6 476 77 */

 1 #include <stdio.h> 2 int main() 3 { 4     int e[10][10],dis[10],book[10],i,j,n,m,t1,t2,t3,u,v,min; 5     int inf=999; //用inf(infinity的缩写)存储一个我们认为的正无穷值 6     //读入n和m，n表示顶点个数，m表示边的条数 7     scanf("%d %d",&n,&m); 8      9     //初始化10     for(i=1;i<=n;i++)11         for(j=1;j<=n;j++)12             if(i==j) e[i][j]=0;  13               else e[i][j]=inf;14               15     //读入边16     for(i=1;i<=m;i++)17     {18         scanf("%d %d %d",&t1,&t2,&t3);19         e[t1][t2]=t3;20     }21 22     //初始化dis数组，这里是1号顶点到其余各个顶点的初始路程23     for(i=1;i<=n;i++)24         dis[i]=e[1][i];25 26     //book数组初始化27     for(i=1;i<=n;i++)28         book[i]=0;29     book[1]=1;30 31         for(j=1;j<=n;j++)32             printf("%5d",dis[j]);33         printf("\n"); //34     35     //Dijkstra算法核心语句36     for(i=1;i<=n-1;i++)37     {38         //找到离1号顶点最近的顶点39         min=inf;40         for(j=1;j<=n;j++)41         {42             if(book[j]==0 && dis[j]<min) //在集合Q中找到最近的顶点43             {44                 min=dis[j];45                 u=j; //记录下顶点位置46             }47         }48         book[u]=1; //顶点u加入集合P49         for(v=1;v<=n;v++)50         {51             if(e[u][v]<inf) //对每个出边指向点52             {53                 if(dis[v]>dis[u]+e[u][v]) 54                     dis[v]=dis[u]+e[u][v]; //松弛55             }56         }57         for(j=1;j<=n;j++)58             printf("%5d",dis[j]);59         printf("\n"); //60     }61        62     getchar(); getchar();63     return 0;64 }65 66 /*67 68 6 969 1 2 170 1 3 1271 2 3 972 2 4 373 3 5 574 4 3 475 4 5 1376 4 6 1577 5 6 478 79 */

 1 #include <stdio.h> 2 int main() 3 { 4     int n,m,i,k; 5     //u、v和w的数组大小要根据实际情况来设置，要比m的最大值要大1 6     int u[60],v[60],w[60]; 7     //first和next的数组大小要根据实际情况来设置，要比n的最大值要大1 8     int first[50],next[50]; 9     scanf("%d %d",&n,&m);10     //初始化first数组下标1~n的值为-1，表示1~n顶点暂时都没有边11     for(i=1;i<=n;i++)12         first[i]=-1;13     for(i=1;i<=m;i++)14     {15         scanf("%d %d %d",&u[i],&v[i],&w[i]);//读入每一条边16         //下面两句是关键啦17         next[i]=first[u[i]];18         first[u[i]]=i;19     }20 21     for(i=1;i<=n;i++)22     {23         k=first[i];24         while(k!=-1)25         {26             printf("%d is : %d %d %d\n",i,u[k],v[k],w[k]);27             k=next[k];28         }29         printf("\n");30     }  31 32     getchar();  getchar();33     return 0;34 }35 36 /*37 38 4 539 1 4 940 4 3 841 1 2 542 2 4 643 1 3 744 45 p155 的图，第二组测试数据46 47 6 948 1 2 149 1 3 1250 2 3 951 2 4 352 3 5 553 4 3 454 4 5 1355 4 6 1556 5 6 457 58 */

 1 #include <stdio.h> 2 int main() 3 { 4     int dis[10],i,k,n,m,u[10],v[10],w[10]; 5     int inf=99999999; //用inf(infinity的缩写)存储一个我们认为的正无穷值 6     //读入n和m，n表示顶点个数，m表示边的条数 7     scanf("%d %d",&n,&m); 8    9     //读入边10     for(i=1;i<=m;i++)11         scanf("%d %d %d",&u[i],&v[i],&w[i]);12 13     //初始化dis数组，这里是1号顶点到其余各个顶点的初始路程14     for(i=1;i<=n;i++)15         dis[i]=inf;16     dis[1]=0;17 18     //Bellman-Ford算法核心语句19     for(k=1;k<=n-1;k++)20       for(i=1;i<=m;i++)21         if( dis[v[i]] > dis[u[i]] + w[i] )22           dis[v[i]] = dis[u[i]] + w[i];23 24     //输出最终的结果25     for(i=1;i<=n;i++)26         printf("%d ",dis[i]);27         28     getchar();29     getchar();30     return 0;31 }32 33 /*34 35 5 536 2 3 237 1 2 -338 1 5 539 4 5 240 3 4 341 42 */

 1 #include <stdio.h> 2 int main() 3 { 4     int dis[10],i,k,n,m,u[10],v[10],w[10]; 5     int inf=999; //用inf(infinity的缩写)存储一个我们认为的正无穷值 6     //读入n和m，n表示顶点个数，m表示边的条数 7     scanf("%d %d",&n,&m); 8    9     //读入边10     for(i=1;i<=m;i++)11         scanf("%d %d %d",&u[i],&v[i],&w[i]);12 13     //初始化dis数组，这里是1号顶点到其余各个顶点的初始路程14     for(i=1;i<=n;i++)15         dis[i]=inf;16     dis[1]=0;17 18     //Bellman-Ford算法核心语句19     for(k=1;k<=n-1;k++)20     {21       for(i=1;i<=m;i++)22         if( dis[v[i]] > dis[u[i]] + w[i] )23           dis[v[i]] = dis[u[i]] + w[i];24       //输出中间结果25       for(i=1;i<=n;i++)26           printf("%5d",dis[i]);27       printf("\n");28     }29         30     getchar(); getchar();31     return 0;32 }33 34 /*35 36 5 537 2 3 238 1 2 -339 1 5 540 4 5 241 3 4 342 43 测试p155的图44 45 6 946 1 2 147 1 3 1248 2 3 949 2 4 350 4 3 451 3 5 552 4 5 1353 4 6 1554 5 6 455 56 与读入边的顺序，很有关系：57 58 6 959 4 6 1560 5 6 461 2 4 362 4 3 463 3 5 564 4 5 1365 1 2 166 1 3 1267 2 3 968 69 */

 1 #include <stdio.h> 2 int main() 3 { 4     int dis[10],i,k,n,m,u[10],v[10],w[10]; 5     int bak[10],check,flag; // 6     int inf=99999999; //用inf(infinity的缩写)存储一个我们认为的正无穷值 7     //读入n和m，n表示顶点个数，m表示边的条数 8     scanf("%d %d",&n,&m); 9   10     //读入边11     for(i=1;i<=m;i++)12         scanf("%d %d %d",&u[i],&v[i],&w[i]);13 14     //初始化dis数组，这里是1号顶点到其余各个顶点的初始路程15     for(i=1;i<=n;i++)16         dis[i]=inf;17     dis[1]=0;18 19     //Bellman-Ford算法核心语句20     for(k=1;k<=n-1;k++)21     {22       //备份23       for(i=1;i<=n;i++) bak[i]=dis[i];24       //松弛25       for(i=1;i<=m;i++)26         if( dis[v[i]] > dis[u[i]] + w[i] )27           dis[v[i]] = dis[u[i]] + w[i];28       //检测dis数组是否有更新29       check=0;30       for(i=1;i<=n;i++)31         if(bak[i]!=dis[i]) 32         {33           check=1;34           break;35         }36       if(check==0) break; //如无更新，跳出循环37     }38     //检测负权回路39     flag=0;40     for(i=1;i<=m;i++)41       if(dis[v[i]] > dis[u[i]]+w[i]) flag=1;42         43     if(flag==1) printf("have fqhl");44     else45     {46       //输出最终的结果47       for(i=1;i<=n;i++)48         printf("%d ",dis[i]);49     }    50     getchar();  getchar();51     return 0;52 }53 54 /*55 56 5 657 2 3 258 1 2 -359 1 5 560 4 5 261 3 4 362 4 3 -863 64 */

 1 #include <stdio.h> 2 int main() 3 { 4   int n,m,i,k; 5   int u[8],v[8],w[8]; 6   int first[6],next[8]; 7   int dis[6]={0},book[6]={0}; 8   int que[101]={0},head=1,tail=1; 9   int inf=99999999;10   11   //读入n和m，n表示顶点个数，m表示边的条数12   scanf("%d %d",&n,&m);13   14   //初始化dis数组，这里是1号顶点到其余各个顶点的初始路程15   for(i=1;i<=n;i++)16     dis[i]=inf;17   dis[1]=0;  18   19   for(i=1;i<=n;i++) book[i]=0;20     21   for(i=1;i<=n;i++) first[i]=-1;22   23   //读入边24   for(i=1;i<=m;i++)25   {26     scanf("%d %d %d",&u[i],&v[i],&w[i]);27     //28     next[i]=first[u[i]];29     first[u[i]]=i;30   }31 32   que[tail]=1; tail++;33   book[1]=1;34   35   while(head<tail)36   {37     k=first[que[head]];38     while(k!=-1)39     {40       if( dis[v[k]] > dis[u[k]] + w[k] )41       {42         dis[v[k]] = dis[u[k]] + w[k];43         //44         if(book[v[k]]==0)45         {46           que[tail]=v[k];47           tail++;48           book[v[k]]=1;49         }50       }51       k=next[k];52     }53     book[que[head]]=0;54     head++;55   }56   57   //输出最终的结果58   for(i=1;i<=n;i++)59     printf("%d ",dis[i]);60   getchar();  getchar();61   return 0;62 }63 64 /*65 66 5 767 1 2 268 1 5 1069 2 3 370 2 5 771 3 4 472 4 5 573 5 3 674 75 */