首页 > 代码库 > POJ Stockbroker Grapevine 1125 多源最短路（Floyd）

POJ Stockbroker Grapevine 1125 多源最短路（Floyd）

2024-08-06 07:17:10   219人阅读

题目大意：

股票经纪人散播谣言，总共n个人，问哪个经纪人能最快的传播谣言，然后输出那个人的编号和所散播谣言的最短时间， 假如每个点都无法全部散播的话则输出 "disjoint"

题目分析：

我们用Floyd求出每个点的最短路，

然后搜索每个点，看和这个点所连接点的最长时间就是这个人散播最后谣言的时间

然后从所有的点中找出时间最长的点

 

 1 #include <iostream> 2 #include <cmath> 3 #include <cstring> 4 #include <cstdlib> 5 #include <cstdio> 6 #include <algorithm> 7 #include <vector> 8 #include <queue> 9 using namespace std;10 #define INF 0xfffffff11 #define maxn 15012 13 int G[maxn][maxn];14 int n;15 16 void Floyd()17 {18     for(int k=1; k<=n; k++)19     {20         for(int i=1; i<=n; i++)21         {22             for(int j=1; j<=n; j++)23             {24                 G[i][j] = min(G[i][j],G[i][k] + G[k][j]);25             }26         }27     }28     int Min = INF, index = 1;29 30     for(int i=1; i<=n; i++)31     {32         int Max = 0;33         for(int j=1; j<=n; j++)34         {35             Max = max(Max,G[i][j]);36         }37         if(Max < Min)38         {39             Min = Max;40             index = i;41         }42     }43 44     if(Min == INF)45         printf("disjoint\n");46     else47         printf("%d %d\n",index,Min);48 49 }50 void Init()51 {52     for(int i=0; i<=n; i++)53     {54         G[i][i] = 0;55         for(int j=0; j<i; j++)56             G[i][j] = G[j][i] = INF;57     }58 }59 60 int main()61 {62     while(cin >> n, n)63     {64         int t, e, w;65         Init();66         for(int i=1; i<=n; i++)67         {68             cin >> t;69             for(int j=0; j<t; j++)70             {71                 cin >> e >> w;72                 G[i][e] = min(G[i][e],w);73             }74         }75 76         Floyd();77 78     }79     return 0;80 }

 

POJ Stockbroker Grapevine 1125 多源最短路（Floyd）


联系
我们