最短路

HDU 1599 find the mincost route

昨天晚上从Yasola那里偷来的一道题……

为什么Yasola这么优秀啊!!!!!
求求你别学了,我已经完全跟不上了……

因为看着题目并不是很难我也就写了一蛤,然后自以为是无脑题就疯狂WA……

emmmm…… 其实仔细想想还是挺简单的。

题意:
给你一张无向图,要你找出最小环。

点数 \( n \leq 100 \)

思路:
对 floyd 进行简单增加一点代码。
floyd 算法剖解开来就是不断找到一个中间结点使得路径更短。而我们可以在这个中间结点加入最短路之前,将其固定为环上的一个点,这点必定不会被所有最短路夹在中间。


有一个非常显然的问题就是,当我固定一个中间结点的时候,我无法保证我所用的最短路为全局最短路。这个问题显著存在于floyd初期。

比如说
存在一个 ABCA 的环与一个 BCDB,其中 \( BD + DC < BC , AB + AC < BC \),而当我使 A 为固定结点,而我的 D 还不曾成为固定结点,也就不会被加入 BC 的最短路。

然而实际上并不要担心,这个环仍然会在floyd后期进行更新,因为对一个环来说,总存在最后一个被作为固定结点。
假设最糟糕的情况,D 结点是 ABCD 结点中最后一个被作为固定结点,那么不也能成功加入 BAC这条最短路径么。

AC Code

#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;

const int inf = 1e8;
const int maxn = 105;

int G[maxn][maxn];
int dis[maxn][maxn];

int main()
{
    int n, m, u, v, w;
    while (scanf("%d %d", &n, &m) != EOF) {
        range(i, 1, n) range(j, 1, n) G[i][j] = i == j ? 0 : inf;
        while (m--) {
            scanf("%d %d %d", &u, &v, &w);
            G[u][v] = G[v][u] = min(G[u][v], w);
        }
        range(i, 1, n) range(j, 1, n) dis[i][j] = G[i][j];
        int ans = inf;
        range(k, 1, n)
        {
            range(i, 1, k - 1) range(j, i + 1, k - 1) ans = min(ans, dis[i][j] + G[i][k] + G[k][j]);
            range(i, 1, n) range(j, 1, n) dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
        }
        ans == inf ? printf("It's impossible.\n") : printf("%d\n", ans);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注