POJ 1125Stockbroker Grapevine（floyd最短路）

本文主要是介绍POJ 1125Stockbroker Grapevine（floyd最短路），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目地址：http://poj.org/problem?id=1125

英语真是硬伤啊。看了好长时间没看懂什么意思。。还是靠着网上的翻译。。。题目很简单，就是求从谁开始通风报信的最长时间最短，并输出耗时最长的环节。

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <queue>
#include <map>
#include<algorithm>using namespace std;
int n, mp[500][500], maxint=99999999;
void floyd()
{int i, j, k;for(k=1;k<=n;k++){for(i=1;i<=n;i++){for(j=1;j<=n;j++){if(mp[i][j]>mp[i][k]+mp[k][j])mp[i][j]=mp[i][k]+mp[k][j];}}}int min1=9999999, max1=-999999, pos;for(i=1;i<=n;i++){max1=-99999999;for(j=1;j<=n;j++){if(i!=j&&max1<mp[i][j]){max1=mp[i][j];}}if(min1>max1){min1=max1;pos=i;}}printf("%d %d\n",pos,min1);
}
int main()
{int i, a, b, m, j;while(scanf("%d",&n)!=EOF&&n){for(i=1;i<=n;i++){for(j=1;j<=n;j++){mp[i][j]=maxint;}}for(i=1;i<=n;i++){scanf("%d",&m);while(m--){scanf("%d%d",&a,&b);mp[i][a]=b;}}floyd();}return 0;
}

这篇关于POJ 1125Stockbroker Grapevine（floyd最短路）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---