hdu 3631 Shortest Path

floyd算法好像很奇妙的样子。可以做到每次加入一个点再以这个点为中间点去更新最短路，效率是n*n。

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

const int maxn = 305;
const int INF = 0x7FFFFFFF;
int A[maxn][maxn], flag[maxn];
int n, m, q;

void floyd(int x)
{
    int i, j;
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < n; j++)
        {
            if (i == x || j == x) continue;
            if (A[i][x] == INF || A[x][j] == INF) continue;
            if (A[i][x] + A[x][j] < A[i][j]) A[i][j] = A[i][x] + A[x][j];
        }
    }
}

int main()
{
    int i, j, u, v, c, koko = 1;
    while (~scanf("%d%d%d", &n, &m, &q))
    {
        if (n == 0 && m == 0 && q == 0) break;
        memset(flag, 0, sizeof(flag));
        for (i = 0; i <= n; i++)
        {
            for (j = 0; j <= n; j++)
            {
                if (i == j) A[i][j] = 0;
                else A[i][j] = INF;
            }
        }
        for (i = 0; i < m; i++)
        {
            scanf("%d%d%d", &u, &v, &c);
            if (c < A[u][v]) A[u][v] = c;
        }
        int oo, pp, qq;
        if (koko != 1) printf("
");
        printf("Case %d:
", koko++);
        for (i = 0; i < q; i++)
        {
            scanf("%d", &oo);
            if (oo == 0)
            {
                scanf("%d", &pp);
                if (flag[pp] == 1) printf("ERROR! At point %d
", pp);
                else if (flag[pp] == 0){ flag[pp] = 1; floyd(pp); }
            }
            else if (oo == 1)
            {
                scanf("%d%d", &pp, &qq);
                if (flag[pp] == 0 || flag[qq] == 0)printf("ERROR! At path %d to %d
", pp, qq);
                else
                {
                    if (A[pp][qq] == INF) printf("No such path
");
                    else printf("%d
", A[pp][qq]);
                }
            }
        }
    }
    return 0;
}