POJ 1125 Stockbroker Grapevine Floyd .

题目地址：http://poj.org/problem?id=1125

找出能让所有人知道消息的且最快的那个人，还要记录那个人传播中耗时间最长的另一人

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int INF=1000000000;
const int maxn=100+5;
int dist[maxn][maxn];
int G[maxn][maxn];  //保存图 (邻接矩阵)
int Floyd(int n)
{for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){if(G[i][j]==0) dist[i][j]=INF;else dist[i][j]=G[i][j];}for(int k=1;k<=n;k++)  //中间经过k-1个点for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
}
bool solve(int n)
{int MinT=INF,MaxT,Max;int pMin,rMax;for(int i=1;i<=n;i++){int sum=0,MaxT=0;for(int j=1;j<=n;j++){if(i==j) continue;sum+=dist[i][j];if(dist[i][j]>MaxT){MaxT=dist[i][j];}if(sum>MinT) break;}if(MinT>sum) {pMin=i;MinT=sum;Max=MaxT;}}if(MinT>=INF) return false;cout<<pMin<<' '<<Max<<endl;return true;
}
int main()
{int n,u,v,w,m;while(cin>>n,n){memset(G,0,sizeof(G));for(int u=1;u<=n;u++){cin>>m;while(m--){cin>>v>>w;G[u][v]=w;}}Floyd(n);if(!solve(n)) cout<<"disjoint"<<endl;}return 0;
}