首页 > 代码库 > HDU 1599 find the mincost route （Floyd求最小环） >>

HDU 1599 find the mincost route （Floyd求最小环） >>

2024-07-16 22:34:13   226人阅读

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
 

Floyd算法保证了在枚举第k个的时候，前k-1个点的dp[i][j]已经全部被计算，也就是说，不经过第k个点的dp[i][j]都已经算出，那么再求出从i到k的权值加上从j到k的权值加上dp[i][j]，不断的更新这个值，就是最终的最小环。


#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <stack>
#define lson o<<1, l, m
#define rson o<<1|1, m+1, r
using namespace std;
typedef long long LL;
const int maxn = 105;
const int MAX = 1000001;
const int mod = 1000000007;
int n, m;
int dp[maxn][maxn], w[maxn][maxn];
int main()
{
    while(~scanf("%d%d", &n, &m)) {
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                w[i][j] = MAX;
        for(int i = 0; i < m;i++){
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            if(c < w[a][b]) w[a][b] = w[b][a] = c;
        }
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                dp[i][j] = w[i][j];
        int ans = MAX;
        for(int k = 1; k <= n; k++) {
            for(int i = 1; i < k; i++)
                for(int j = i+1; j < k; j++)
                    ans = min( w[i][k]+w[k][j]+dp[i][j], ans );
            for(int i = 1; i <= n; i++)
                for(int j = 1; j <= n; j++)
                    dp[i][j] = min( dp[i][j], dp[i][k]+dp[k][j] );
        }
        if(ans != MAX) printf("%d\n", ans);
        else printf("It's impossible.\n");
    }
    return 0;
}





联系
我们