老田用的弗洛伊德 我觉得我的快一点..不知道叫啥算法 无招胜有招了 (墨镜)
每个人身上两种属性 传到他需要的时间(int time)以及他是否往下传播(bool set)
unit向他的contact传播 => contact.time=unit.settime
[contact](传播到此contact所需时间)+unit.time
1.开始选择的人start, start.set=true
2.扫描所有的unit, 如果set==true则对他的每一个contact判断, 若contact.time>unit.time+unit.setting(contact), 则用这个较快的time赋值,并且contact.set=true, 下一轮用新的time传播给这个contact的contact们
3.重复2知道所有unit.set==false为止
4.判断是否有unit没有触及到
#include <cstdio> typedef struct unit { int num; int contact[99]; int settime[99]; bool set; int time; } Unit; typedef struct aa { int start; int time; } Result; void calc(); int search(); Unit a[101]; Result x,result; int n; int main() { int i,j,start; scanf("%d",&n); while(n) { for(i=1;i<=n;i++) { scanf("%d",&a[i].num); for(j=0;j<a[i].num;j++) scanf("%d%d",&a[i].contact[j],&a[i].settime[j]); } result.start=-1; for(start=1;start<=n;start++) { for(i=1;i<=n;i++) { a[i].set=false; a[i].time=-1; } a[start].set=true; a[start].time=0; i=0; while(i<n+1) { calc(); for(i=1;i<=n;i++) if(a[i].set==true) break; } x.time=search(); x.start=start; for(i=1;i<=n;i++) if(a[i].time==-1) { x.start=-1; break; } if(x.start==-1) continue; if(x.time<result.time||result.start==-1) result=x; } if(result.start==-1) if(n==0) printf("0 0\n"); else printf("disjoint\n"); else printf("%d %d\n",result.start,result.time); scanf("%d",&n); } return 0; } void calc() { int i,j,spreadtime; for(i=1;i<=n;i++) if(a[i].set) { for(j=0;j<a[i].num;j++) { spreadtime=a[i].time+a[i].settime[j]; if(a[a[i].contact[j]].time>spreadtime||a[a[i].contact[j]].time==-1) { a[a[i].contact[j]].time=spreadtime; a[a[i].contact[j]].set=true; } } a[i].set=false; } } int search() { int max,i; max=a[1].time; for(i=2;i<=n;i++) if(a[i].time>max) max=a[i].time; return max; }