python/TangDou/Topic/HDU3631.cpp

#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
const int N = 310;
int t, n, m, q;
int g[N][N];
bool flag[N]; // 记录是否标记
int a, b, c;

void floyd(int k) { // 以k为中转节点进行转移
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (g[i][j] > g[i][k] + g[k][j])
                g[i][j] = g[i][k] + g[k][j];
}

int main() {
    // 加快读入
    ios::sync_with_stdio(false), cin.tie(0);
    while (cin >> n >> m >> q && n + m + q) {
        if (t) printf("\n"); // 谜之格式
        printf("Case %d:\n", ++t);

        // 整体正无穷，对角线清零
        memset(g, inf, sizeof g);
        for (int i = 0; i <= n; i++) g[i][i] = 0;

        memset(flag, false, sizeof flag);

        while (m--) {
            cin >> a >> b >> c;
            g[a][b] = min(c, g[a][b]); // floyd也可以跑有向图
        }
        while (q--) {
            cin >> c;
            if (c == 0) {
                cin >> a;
                if (flag[a]) // 如果a已经被标记过了
                    printf("ERROR! At point %d\n", a);
                else {
                    flag[a] = true; // 标记上
                    floyd(a);       // 通过a进行其它节点转移
                }
            } else {
                cin >> a >> b;
                if (!(flag[a] && flag[b]))
                    printf("ERROR! At path %d to %d\n", a, b);
                else if (g[a][b] == inf)
                    printf("No such path\n");
                else
                    printf("%d\n", g[a][b]);
            }
        }
    }
    return 0;
}