多源最短路pku1125

floyd可以秒杀，虽然其时间复杂度是（n^3）但是n<=100,时间是0ms

#include<stdio.h>

#define MAX 0x3fffffff
int map[105][105];

int main()
{
    int n,i,j,m,next,k;
    while(scanf("%d",&n),n)
    {
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                map[i][j]=MAX;
            }
        }
        
        for(i=1;i<=n;i++)
        {
            scanf("%d",&m);
            for(j=1;j<=m;j++)
            {
                scanf("%d",&next);
                scanf("%d",&map[i][next]);
            }
        }

        for(k=1;k<=n;k++)
        {
            for(i=1;i<=n;i++)
            {
                for(j=1;j<=n;j++)
                {
                    if(map[i][j]>map[i][k]+map[k][j])
                        map[i][j]=map[i][k]+map[k][j];
                }
            }
        }
        int max=0,ji=0,min=MAX;
        for(i=1;i<=n;i++)
        {
            max=0;
            for(j=1;j<=n;j++)
            {
                if(i!=j)
                if(map[i][j]>max)
                {
                    max=map[i][j];
                }
            }
            if(min>max)
            {
                min=max;
                ji=i;
            }
        }
        printf("%d %d\n",ji,min);
    }
}