soj2427floyed算法.cpp

来自「一些ACM题目的解答,主要是soj和poj的」· C++ 代码 · 共 55 行

#include<stdio.h>

#define NIL 99999999
int main(void)
{
    int n,m;
    
    while(scanf("%d%d",&n,&m)==2&&(n||m))
    {
        int num[101][101]={0};
        int i;
        for(i=1;i<=m;i++)
        {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            num[a][b]=c;
            num[b][a]=c;
        }
        int u,v;
        int dist[101][101]={0};
        for(u=1;u<=n;u++)
        {
            for(v=1;v<=n;v++)
            {
                dist[u][v] = (u!=v&&num[u][v] == 0) ? NIL : num[u][v];
            }
        }
        int k,j;
        for(k=1;k<=n;k++)
        {
            for(i=1;i<=n;i++)
            {
                for(j=1;j<=n;j++)
                {
                    if(dist[i][k]+dist[k][j] < dist[i][j])
                    {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }
        scanf("%d",&k);
        while(k--)
        {
            scanf("%d%d",&i,&j);
            if(num[i][j]==NIL)
                printf("pity\n");
            else
                printf("%d\n",dist[i][j]);
        }
        putchar('\n');
    }
    return 0;
}