floyd 最短路

最新推荐文章于 2024-04-24 22:14:19 发布

JasonChen_ACM

最新推荐文章于 2024-04-24 22:14:19 发布

阅读量424

点赞数 1

分类专栏： ACM:最短路

本文链接：https://blog.csdn.net/JasonChen_ACM/article/details/51438756

版权

ACM:最短路专栏收录该内容

1 篇文章

订阅专栏


  
  
   
   Problem Description
  
  
  
  
   
   在每年的校赛里，所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候，却是非常累的！所以现在他们想要寻找最短的从商店到赛场的路线，你可以帮助他们吗？


  
  
  
  
   
    
  
  
  
  

  
  
  
  
   
   Input
  
  
  
  
   
   输入包括多组数据。每组数据第一行是两个整数N、M（N<=100，M<=10000），N表示成都的大街上有几个路口，标号为1的路口是商店所在地，标号为N的路口是赛场所在地，M则表示在成都有几条路。N=M=0表示输入结束。接下来M行，每行包括3个整数A，B，C（1<=A,B<=N,1<=C<=1000）,表示在路口A与路口B之间有一条路，我们的工作人员需要C分钟的时间走过这条路。
 输入保证至少存在1条商店到赛场的路线。

  
  
  
  
   
    
  
  
  
  

  
  
  
  
   
   Output
  
  
  
  
   
   对于每组输入，输出一行，表示工作人员从商店走到赛场的最短时间
  
  
  
  
   
    
  
  
  
  

  
  
  
  
   
   Sample Input
  
  
 
 
  
      
    
     
     2 1
1 2 3
3 3
1 2 5
2 3 5
3 1 2
0 0
    
    
 
 
 
 
  
   
 
 
 
 
  
  

 
 
 
 
  
  Sample Output
 
 
 
 
  
     
   
    
    3
2
   
   
 
 
 
 
  
   
 
 
 
 
  
  

 
 
 
 
  
  

 
 
 
 
  
  

 
 
 
 
  
  代码：：
 
 
 
 
  
  

 
 
 
 
  
  
   
   #include<iostream>
   
   
using namespace std;
   
   
#define  INF 10000009
  
  
  
  
   
   

  
  
  
  
   
   int d[105][105]; //定义存图数组。
   
   
int n,m;
   
   
void init()
   
   
{
   
   
    for(int i=0; i<n; i++)
   
   
        for(int j=0; j<n; j++)
   
   
            d[i][j]=(i==j?0:INF); //数组赋初值。
  
  
  
  
   
   

  
  
  
  
   
   }
  
  
  
  
   
   

  
  
  
  
   
   int main()
   
   
{
   
   
    while(cin>>n>>m)
  
  
  
  
   
   

  
  
  
  
   
       {
  
  
  
  
   
   

  
  
  
  
   
           if(n==0&&m==0)  break; //n，m为零跳出。
  
  
  
  
   
   

  
  
  
  
   
           init();
  
  
  
  
   
   

  
  
  
  
   
           int u,v,w;
  
  
  
  
   
   

  
  
  
  
   
           for(int i=0; i<m; i++)
   
   
        {
   
   
            cin>>u>>v>>w;
   
   
            d[u-1][v-1]=w; //u-1到v-1距离为w
  
  
  
  
   
   
            d[v-1][u-1]=w; //v-1到u-1距离为w
  
  
  
  
   
   

  
  
  
  
   
           }
  
  
  
  
   
   

  
  
  
  
   
           for(int k=0; k<n; k++)
   
   
            for(int i=0; i<n; i++)
   
   
                for(int j=0; j<n; j++)
   
   
                    if(d[i][k]!=INF&&d[k][j]!=INF)d[i][j]=d[i][j]<(d[i][k]+d[k][j])?d[i][j]:(d[i][k]+d[k][j]);    //两边之和大于第三边，取长边~
  
  
  
  
   
   

  
  
  
  
   
   
        cout<<d[0][n-1]<<endl;
  
  
  
  
   
   

  
  
  
  
   
       }
  
  
  
  
   
   

  
  
  
  
   
   }