首页 > 代码库 > poj 1125 Stockbroker Grapevine(多源最短路)
poj 1125 Stockbroker Grapevine(多源最短路)
链接: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; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。