POJ1125 Stockbroker Grapevine 多源最短路

时间:2021-11-16 07:05:30

题目大意

给定一个图,问从某一个顶点出发,到其它顶点的最短路的最大距离最短的情况下,是从哪个顶点出发?须要多久?

(假设有人一直没有联络,输出disjoint)

解题思路

Floyd不解释

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int INF = 1000000000;
const int maxn = 110;
int d[maxn][maxn];
int n;
int main()
{
//freopen("in.txt","r",stdin);
while(scanf("%d",&n) && n) {
for(int i = 0 ; i < maxn ; i ++) {
fill(d[i],d[i]+maxn,INF);
}
for(int i = 0 ; i < maxn ; i ++) d[i][i] = 0;
for(int i = 1 ; i <= n ; i ++) {
int t;
scanf("%d",&t);
while(t--) {
int a,b;
scanf("%d%d",&a,&b);
d[i][a] = b;
}
}
for(int k = 1 ; k <= n ; k ++) {
for(int i = 1 ; i <= n ; i ++) {
for(int j = 1 ; j <= n ; j ++) {
d[i][j] = min(d[i][j],d[i][k]+d[k][j]);
}
}
}
int mi = INF;
int mark;
for(int i = 1 ; i <= n ; i ++) {
int ma = -1;
for(int j = 1 ; j <= n ; j ++) {
if(ma < d[i][j]) ma = d[i][j];
}
if(ma < mi) {
mi = ma;
mark = i;
}
}
if(mi < INF) {
printf("%d %d\n",mark,mi);
}else printf("disjoint\n");
}
return 0;
}