本文主要是介绍poj1125 floyd，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
如题：http://poj.org/problem?id=1125
| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 28384 | Accepted: 15750 |
Description
Unfortunately for you, stockbrokers only trust information coming from their "Trusted sources" This means you have to take into account the structure of their contacts when starting a rumour. It takes a certain amount of time for a specific stockbroker to pass the rumour on to each of his colleagues. Your task will be to write a program that tells you which stockbroker to choose as your starting point for the rumour, as well as the time it will take for the rumour to spread throughout the stockbroker community. This duration is measured as the time needed for the last person to receive the information.
Input
Each person is numbered 1 through to the number of stockbrokers. The time taken to pass the message on will be between 1 and 10 minutes (inclusive), and the number of contacts will range between 0 and one less than the number of stockbrokers. The number of stockbrokers will range from 1 to 100. The input is terminated by a set of stockbrokers containing 0 (zero) people.
Output
It is possible that your program will receive a network of connections that excludes some persons, i.e. some people may be unreachable. If your program detects such a broken network, simply output the message "disjoint". Note that the time taken to pass the message from person A to person B is not necessarily the same as the time taken to pass it from B to A, if such transmission is possible at all.
Sample Input
3 2 2 4 3 5 2 1 2 3 6 2 1 2 2 2 5 3 4 4 2 8 5 3 1 5 8 4 1 6 4 10 2 7 5 2 0 2 2 5 1 5 0
Sample Output
3 2 3 10
Source
题目大意：求出所给有向图某一点到其他所有点所花费的时间中最大的那一个最小。
思路：floyd水过
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define MAXN 105
#define INF 0x0fffffff
int n,m;
int map[MAXN][MAXN];
int main()
{
// freopen("C:\\1.txt","r",stdin);
while(~scanf("%d",&n))
{
if(!n)
break;
int i,j,k;
for(i=0;i<MAXN;i++)
for(j=0;j<MAXN;j++)
map[i][j]=INF;
for(i=1;i<=n;i++)
map[i][i]=0;
for(i=1;i<=n;i++)
{
scanf("%d",&m);
for(j=0;j<m;j++)
{
int v,cost;
scanf("%d%d",&v,&cost);
map[i][v]=cost;
}
}
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(map[i][j]>map[i][k]+map[k][j])
map[i][j]=map[i][k]+map[k][j];
int d[MAXN]={0};
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(map[i][j]>d[i])
d[i]=map[i][j];
int v,min=INF;
for(i=1;i<=n;i++)
if(min>d[i])
{
min=d[i];
v=i;
}
if(min==INF)
printf("disjoint\n");
else
printf("%d %d\n",v,min);
}
}
这篇关于poj1125 floyd的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
