首页 > 代码库 > POJ Stockbroker Grapevine（floyd）
POJ Stockbroker Grapevine（floyd）
https://vjudge.net/problem/POJ-1125
题意：
题意不是很好理解，首先输入一个n，表示有n个股票经纪人，接下来输入n行，每行第一个数m为该股票经纪人认识的经纪人数，然后输入m对数（a，t），表示第i个经纪人把消息传给第a个经纪人所需要的时间。
计算将消息传遍所有人所需要的最少时间。
思路：
起点任意，用floyd比较好。因为floyd求出的是每两点之间的最短路，所以最后计算最小时间时，需要先取最大值，比如说1号经纪人为起点，因为谁都可能为终点，所以枚举所有人，将最大时间作为最小时间，这个应该不难理解。
1 #include<iostream> 2 #include<algorithm> 3 #include<string> 4 #include<cstring> 5 using namespace std; 6 7 const int maxn = 100 + 5; 8 const int INF = 0x3f3f3f3f; 9 10 int n;11 int d[maxn][maxn];12 13 14 void floyd()15 {16 for (int k = 1; k <= n;k++)17 for (int i = 1; i <= n;i++)18 for (int j = 1; j <= n; j++)19 d[i][j] = min(d[i][j], d[i][k] + d[k][j]);20 }21 22 int main()23 {24 //freopen("D:\\txt.txt", "r", stdin);25 int x, a, t;26 while (~scanf("%d", &n) && n)27 {28 for (int i = 1; i <= n; i++)29 {30 d[i][i] = 0;31 for (int j = 1; j < i; j++)32 d[i][j] = d[j][i] = INF;33 }34 35 for (int i = 1; i <= n; i++)36 {37 scanf("%d", &x);38 while (x--)39 {40 scanf("%d%d", &a, &t);41 d[i][a] = t;42 }43 }44 45 floyd();46 int stock;47 int ans = INF;48 for (int i = 1; i <= n; i++)49 {50 int MAX = 0;51 for (int j = 1; j <= n; j++)52 {53 if (i == j) continue;54 MAX = max(MAX, d[i][j]);55 }56 if (ans > MAX)57 {58 ans = MAX;59 stock = i;60 }61 }62 if (ans == INF)63 printf("disjoint\n");64 else65 printf("%d %d\n", stock, ans);66 }67 return 0;68 }
POJ Stockbroker Grapevine（floyd）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。