本文主要是介绍poj1125 floyd，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
如题：http://poj.org/problem?id=1125
在一群人中散布传言，求某一个人 到 所有人散布传言的时间最短
用floyd求出每一个人到所有人的最短路径，再在可以传到所有人的人中找出最短路径中最大值，在再这些最大值中取最小值，就是最少耗时的时间.
#include<iostream>
using namespace std;
#define MAX(x,y)((x)>(y)?(x):(y))
#define MIN(x,y)((x)<(y)?(x):(y))
#define inf 0x0fffffff
int p[105][105],n;
int main()
{
int i,j,k;
while(scanf("%d",&n)&&n)
{
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
p[i][j]=inf;
p[i][i]=0;
}
for(i=1;i<=n;i++)
{
int m,j,val;
scanf("%d",&m);
while(m--)
{
scanf("%d %d",&j,&val);
p[i][j]=val;
}
}
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
p[i][j]=MIN(p[i][j],p[i][k]+p[k][j]);
int t=0,temp=inf;
for(i=1;i<=n;i++)
{
int mm=0;
for(j=1;j<=n;j++)
mm=MAX(p[i][j],mm);
if(temp>mm)
{
temp=mm;
t=i;
}
}
if(t)
printf("%d %d\n",t,temp);
else
printf("disjoint\n");
}
}
这篇关于poj1125 floyd的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
