首页 > ACM题库 > HDU-杭电 > HDU 1599 find the mincost route-最短路径-[解题报告] C++
2013
12-12

HDU 1599 find the mincost route-最短路径-[解题报告] C++

find the mincost route

问题描述 :

杭州有N个景区,景区之间有一些双向的路来连接,现在8600想找一条旅游路线,这个路线从A点出发并且最后回到A点,假设经过的路线为V1,V2,….VK,V1,那么必须满足K>2,就是说至除了出发点以外至少要经过2个其他不同的景区,而且不能重复经过同一个景区。现在8600需要你帮他找一条这样的路线,并且花费越少越好。

输入:

第一行是2个整数N和M(N <= 100, M <= 1000),代表景区的个数和道路的条数。
接下来的M行里,每行包括3个整数a,b,c.代表a和b之间有一条通路,并且需要花费c元(c <= 100)。

输出:

对于每个测试实例,如果能找到这样一条路线的话,输出花费的最小值。如果找不到的话,输出"It’s impossible.".

样例输入:

3 3
1 2 1
2 3 1
1 3 1
3 3
1 2 1
1 2 3
2 3 1

样例输出:

3
It's impossible.

求无向图的最小环。。。。

floyd。。。。

具体见代码。。。

#include<iostream>
 const int N=111;
 const int inf=1000000;
 #define min(x,y) ((x<y)?(x):(y));
 using namespace std;
 
 int dist[N][N];
 int edge[N][N];
 int n,m;
 
 void floyd(){
     int ans=inf;
     for(int i=1;i<=n;i++){
         for(int j=1;j<=n;j++){
             dist[i][j]=edge[i][j];
         }
     }
     //根据Floyed的原理,在最外层循环做了k-1次之后,dis[i][j]则代表了i到j的路径中所有结点编号都小于k的最短路径
     for(int k=1;k<=n;k++){
         //环的最小长度为edge[i][k]+edge[k][j]+i->j的路径中所有编号小于k的最短路径长度
         for(int i=1;i<k;i++){
             for(int j=i+1;j<k;j++){
                 if(dist[i][j]+edge[i][k]+edge[k][j]<inf){
                     ans=min(ans,dist[i][j]+edge[i][k]+edge[k][j]);
                 }
             }
         }
         //floyd原来的部分,更新dist[i][j]///
         for(int i=1;i<=n;i++){
             for(int j=1;j<=n;j++){
                 if(dist[i][j]>dist[i][k]+dist[k][j]){
                     dist[i][j]=dist[i][k]+dist[k][j];
                 }
             }
         }
     }
     if(ans==inf){
         printf("It's impossible.\n");
     }else 
         printf("%d\n",ans);
 }
 
 
 int main(){
     while(scanf("%d%d",&n,&m)!=EOF){
         for(int i=1;i<=n;i++){
             for(int j=1;j<=n;j++){
                 if(i==j){
                     edge[i][j]=0;
                 }else 
                     edge[i][j]=inf;
             }
         }
         int x,y,cost;
         for(int i=1;i<=m;i++){
             scanf("%d%d%d",&x,&y,&cost);
             //考虑重边
             if(edge[x][y]>cost){
                 edge[x][y]=edge[y][x]=cost;
             }
         }
         floyd();
     }
     return 0;
 }

 

解题报告转自:http://www.cnblogs.com/wally/archive/2013/01/31/2886687.html


  1. “再把所有不和该节点相邻的节点着相同的颜色”,程序中没有进行不和该节点相邻的其他节点是否相邻进行判断。再说求出来的也不一样是颜色数最少的

  2. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。