Floyd算法计算每对顶点之间的最短路径的问题

题目中隐含了一个条件是一个人能够同一时候将谣言传递给多个人

题目终于的要求是时间最短。那么就要遍历一遍求出每一个点作为源点时，最长的最短路径长是多少，再求这些值其中最小的是多少，就是题目所求

#include<bits/stdc++.h>

using namespace std;

int n,x,p,t;

int m[120][120],dist[120][120],Max[120];

void floyd(int n,int m[][120],int dist[][120])

{

    for(int i=1;i<=n;i++)

        for(int j=1;j<=n;j++)

        {

            if(m[i][j]!=0)

                dist[i][j]=m[i][j];

            else

                dist[i][j]=INT_MAX;

        }

    for(int k=1;k<=n;k++)

        for(int i=1;i<=n;i++)

            for(int j=1;j<=n;j++)

            {

                if(dist[i][k]!=INT_MAX&&dist[k][j]!=INT_MAX&&dist[i][k]+dist[k][j]<dist[i][j])

                    dist[i][j]=dist[i][k]+dist[k][j];

            }

}

int main()

{

	int n;

	while(scanf("%d",&n)==1&&n)

	{

        memset(m,0,sizeof(m));

        memset(Max,0,sizeof(Max));

	    for(int i=1;i<=n;i++)

        {

            scanf("%d",&x);

            for(int j=1;j<=x;j++)

            {

                scanf("%d%d",&p,&t);

                m[i][p]=t;

            }

        }

        floyd(n,m,dist);

        for(int i=1;i<=n;i++)

            for(int j=1;j<=n;j++)

            {

                if(i!=j&&dist[i][j]>Max[i])

                    Max[i]=dist[i][j];

            }

        int Min=INT_MAX,ans=0;

        for(int i=1;i<=n;i++)

        {

            if(Max[i]<Min)

            {

                Min=Max[i];

                ans=i;

            }

        }

        printf("%d %d\n",ans,Min);

	}

    return 0;

}