poj 1125 Stockbroker Grapevine(多源最短)

时间:2024-09-24 20:34:32

id=1125">链接:poj 1125

题意:输入n个经纪人,以及他们之间传播谣言所需的时间,

问从哪个人開始传播使得全部人知道所需时间最少。这个最少时间是多少

分析:由于谣言传播是同一时候的,对于某条路径使得全部人都知道的时间。不是时间的总和,而是路径中最长的边

从多条路径的最长边,找出最小值。由于为多源最短路,用Floyd比較方便

#include<stdio.h>
#include<limits.h>
int a[105][105];
void floyd(int n)
{
int i,j,k,s,pos;
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(a[i][k]!=INT_MAX&&a[k][j]!=INT_MAX&&a[i][k]+a[k][j]<a[i][j])
a[i][j]=a[i][k]+a[k][j];
k=INT_MAX;
pos=0;
for(i=1;i<=n;i++){
s=0;
for(j=1;j<=n;j++) //先求出路径中的最长边为总传播时间
if(i!=j&&a[i][j]>s)
s=a[i][j];
if(s<k){ //再找出传播时间的最小值
k=s;
pos=i;
}
}
if(k==INT_MAX)
printf("disjoint\n");
else
printf("%d %d\n",pos,k); }
int main()
{
int n,m,i,j,b,t;
while(scanf("%d",&n)!=EOF){
if(n==0)
break;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
a[i][j]=INT_MAX;
for(i=1;i<=n;i++){
scanf("%d",&m);
for(j=1;j<=m;j++){
scanf("%d%d",&b,&t);
a[i][b]=t; //单程
}
}
floyd(n);
}
return 0;
}