最短路 Floyed

求多源最短路的一种方法，经常做预处理用，能处理出来图中任意两个点之间的最短距离，时间复杂度O(n^3) 模板代码：

for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                if (i == k) continue;
                for (int j = 1; j <= n; j++) {
                    if (i == j || k == j) continue;
                    dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
                }
            }
        }

POJ 1125 Stockbroker Grapevine

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

const int maxv = 500 + 5;

int dis[maxv][maxv];


int main() {
    int n, num, v, w;
//    freopen("in.txt", "r", stdin);
    while (scanf("%d", &n) != EOF && n) {
        memset(dis, 0x3f, sizeof(dis));
        for (int u = 1; u <= n; u++) {
            scanf("%d", &num);
            for (int j = 0; j < num; j++) {
                scanf("%d%d", &v, &w);
                dis[u][v] = min(dis[u][v], w);
            }
            dis[u][u] = 0;
        }

        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                if (i == k) continue;
                for (int j = 1; j <= n; j++) {
                    if (i == j || k == j) continue;
                    dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
                }
            }
        }
        bool ok = true;
        int anstime = 0x3f, ansid = 0;
        for (int i = 1; i <= n; i++) {
            int minn = 0;
            for (int j = 1; j <= n; j++) {
                if (i == j) {
                    continue;
                }
                if (dis[i][j] == 0x3f) {
                    ok = false;
                    goto end;
                }
                minn = max(minn, dis[i][j]);
            }
            if (minn < anstime) {
                anstime = minn;
                ansid = i;
            }
        }
end:
        if (ok) {
            printf("%d %d\n", ansid, anstime);
        } else {
            puts("disjoint");
        }

    }
    return 0;
}