最短路

红太狼 2022-08-04 08:28 165阅读 0赞

\[hdu 1599\] ([http://acm.hdu.edu.cn/showproblem.php?pid=1599][http_acm.hdu.edu.cn_showproblem.php_pid_1599])  
题目描述：  
find the mincost route

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

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  
3 3  
1 2 1  
2 3 1  
1 3 1  
3 3  
1 2 1  
1 2 3  
2 3 1

Sample Output  
3  
It’s impossible.

Author  
8600

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

言简意赅：  
8600要去旅行，他会去>=3个景区，且去的地方不能有重复的，且最后还要回到初始点，要求其最小路径；  
算法：  
利用Floyd算法扩展求无向图的最小环；  
注意：有向图最小环和无向图最小环是不一样的，在有向图中两个顶点就能形成最小环，而在无向图中需要三个顶点才能组成最小环。

代码实现：

#include <iostream>
    #include <stdio.h>
    #define MAX 0xfffffff
    
    using namespace std;
    
    int n,m,a,b,c;
    int dist[110][110],map[110][110];
    
    int min(int x,int y)
    {
        return (x<=y)? x:y;
    }
    
    int main()
    {
        int M=MAX/10;
        while(scanf("%d%d",&n,&m)!=EOF)
        {
            int ans=M;
            for(int i=1; i<=n; i++)
            {
                for(int j=1; j<=n; j++)
                {
                    map[i][j]=M;//初始化为无穷大，因为自身不能成环
                }
            }
            while(m--)
            {
                scanf("%d%d%d",&a,&b,&c);
                if(c<map[a][b]) map[a][b]=map[b][a]=c;
            }
            for(int i=1; i<=n; i++)
            {
                for(int j=1; j<=n; j++)
                {
                    dist[i][j]=map[i][j];
                }
            }
            for(int k=1; k<=n; k++)//有前k-1个点递推第k个点的情况//在最短路径外的一点将最短路径首尾相接，那么就得到一个最小环
            {
                for(int i=1; i<k; i++)
                {
                    for(int j=i+1; j<k; j++)//两个点必然是不同的
                    {
                        ans=min(ans,dist[i][j]+map[k][i]+map[k][j]);//k为其中最大点，无向图三点成环，可以求得最小环
                    }
                }
                for(int i=1; i<=n; i++)//利用Floyd算法求任意两点的最短路，包含前k-1个点
                {
                    for(int j=1; j<=n; j++)
                    {
                        dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);//每次都要把最短路径进行更新
                    }
                }
            }
            if(ans==M) printf("It's impossible.\n");
            else printf("%d\n",ans);
        }
        return 0;
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_1599]: http://acm.hdu.edu.cn/showproblem.php?pid=1599