Stockbroker Grapevine（floyd）

题意：

首先，题目可能有多组测试数据，每个测试数据的第一行为经纪人数量N（当N=0时，

输入数据结束），然后接下来N行描述第i（1<=i<=N）个经纪人与其他经纪人的关系

（教你如何画图）。每行开头数字M为该行对应的经纪人有多少个经纪人朋友（该节点

的出度，可以为0），然后紧接着M对整数，每对整数表示成a,b,则表明该经纪人向第a

个经纪人传递信息需要b单位时间（即第i号结点到第a号结点的孤长为b），整张图为

有向图，即弧Vij 可能不等于弧Vji。当构图完毕后，求

当从该图中某点出发，将“消息”传播到整个经纪人网络的最小时间，输出这个经纪

人号和最小时间。最小时间的判定方式为——从这个经纪人（结点）出发，整个经纪

人网络中最后一个人接到消息的时间。如果有一个或一个以上经纪人无论如何无法收

到消息，输出“disjoint”。

 #include<stdio.h>

 #include<string.h>

 const int INF=<<;

 int dis[][],n;

 void init()

 {

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

     {

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

         {

             dis[i][j] = INF;

         }

         dis[i][i] = ;

     }

 }

 void floyd()

 {

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

     {

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

         {

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

             {

                 if (dis[i][j] >  dis[i][k] + dis[k][j])

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

             }

         }

     }

 }

 int main()

 {

     while(~scanf("%d",&n)&&n)

     {

         init();

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

         {

             int m,j,time;

             scanf("%d",&m);

             while(m--)

             {

                 scanf("%d%d",&j,&time);

                 dis[i][j] = time;

             }

         }

         floyd();

         int flag = ,temp = INF;

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

         {

             int max = ;

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

             {

                 if (dis[i][j] > max)

                     max = dis[i][j];

             }

             if (temp > max)

             {

                 flag = i;

                 temp = max;

             }

         }

         if (flag)

             printf("%d %d\n",flag,temp);

         else

             printf("disjoint\n");

     }

     return ;

 }

巴特西

Stockbroker Grapevine（floyd）

最新文章

热门文章