【最短路-判负环 Floyd】Wormholes POJ - 3259

Wormholes POJ - 3259

题意：

给定一些农场及农场间的双向路径及它们花费的时间，再给定一些农场间的单向虫洞路径。当经过一条虫洞路径从A点到达B点时，会回到比从A点出发时更早的时刻。问农夫能否可以通过这些路径见到以前的自己。

思路：

Floyd判负环。

int f;
int n, m, w;
int d[maxn][maxn];

bool floyd() {
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (d[i][j] > d[i][k] + d[k][j]) {
                    d[i][j] = d[i][k] + d[k][j];
                }
            }
            if (d[i][i] < 0) return true;
        }
    }
    return false;
}

int main()
{
   // ios::sync_with_stdio(false);
   /// int t; cin >> t; while (t--) {
    cin >> f;

    while(f--){
        cin >> n >> m >> w;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == j) d[i][j] = 0;
                else d[i][j] = INF;
            }
        }
        for (int j = 1; j <= m; j++) {
            int u, v, t;
            cin >> u >> v >> t;
            if (t < d[u][v]) {
                d[u][v] = d[v][u] = t;
            }
        }
        for (int j = 1; j <= w; j++) {
            int u, v, t;
            cin >> u >> v >> t;
            d[u][v] = -t;
        }
        if (floyd()) cout << "YES\n";
        else cout << "NO\n";
    }
   // }
    return 0;
}

【最短路-判负环 Floyd】Wormholes POJ - 3259

原文：https://www.cnblogs.com/streamazure/p/13405464.html