hdu1599 find the mincost route floyd求出最小权值的环

find the mincost route

Time Limit: 1000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3456 Accepted Submission(s): 1409

Problem Description

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

Input

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

Output

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

Sample Input

Sample Output

3
It's impossible.

Author

8600

Source

HDU 2007-Spring Programming Contest - Warm Up （1）

Recommend

8600 | We have carefully selected several similar problems for you: 1142 1217 1597 1301 1054

本题的题意时汉文，所以翻译就不用嗦说了，大家看看那就知道了，本题求得时给出若个双向图的路径，问你是否具有最短的环，如果有，便输出他的最小长度的，如果没有就输出impossibl

本题如果用dfs进行搜索的话会超时，所以尽量不压迫使用dfs进行搜需，之前在别的oj里见过一个累世的题目，那个题目求得也是最短路径的环但是徐娅萍输出路径，那个提我用dfs过了，但是这道题却过不去，

所以还是只能用floyd做了

下面的代码可以当做末班时用

#include<cstdio>
#include<cstring>
#define find_min(a,b) a<b?a:b

const int N = 101;
const int INF = 0x7ffffff;
int mat[N][N],dist[N][N],pre[N][N],path[N],n;

int main()
{
    int i,j,k,m,a,b,c;
    int num;
    
    while(~scanf("%d%d",&n,&m)){
        for(i=1;i<=n;i++){
            for(j=1;j<=n;j++){
                mat[i][j]=dist[i][j]=INF;
                pre[i][j]=i;
            }
        }
        while(m--){
            scanf("%d%d%d",&a,&b,&c);
            mat[a][b]=mat[b][a]=dist[a][b]=dist[b][a]=find_min(mat[a][b],c);
        }

        int min=INF;
        for(k=1;k<=n;k++){//最短路径外一点将最短路首尾链接,那么就得到一个最小环
            for(i=1;i<k;i++){
                for(j=i+1;j<k;j++){
                    //求最小环不能用两点间最短路松弛,因为(i,k)之间的最短路,(k,j)之间的最短路可能有重合的部分
                    //所以mat[][]其实是不更新的,这里和单纯的floyd最短路不一样
                    //dist[i][j]保存的是 i 到 j 的最短路权值和
                    int tmp=dist[i][j]+mat[i][k]+mat[k][j];//这里 k 分别和 i 还有 j 在mat中直接相连
                    if(tmp<min){
                        min=tmp;
                        num=0;
                        int p=j;
                        while(p!=i){//回溯
                            path[num++]=p;
                            p=pre[i][p];//pre[i][j]表示 i 到 j 最短路径上 j 前面的一个点
                        }
                        path[num++]=i;
                        path[num++]=k;
                    }
                }
            }
            for(i=1;i<=n;i++){
                for(j=1;j<=n;j++){
                    if(dist[i][j]>dist[i][k]+dist[k][j]){
                        dist[i][j]=dist[i][k]+dist[k][j];//dist[][]保存两点间最短距离
                        pre[i][j]=pre[k][j];
                    }
                }
            }
        }
        if(min==INF)puts("It's impossible.");
        else{
            printf("%d
",min);
        }
    }
    return 0;
}