题意: n个人炒股,每个人都可以给其他人报信,第 1 行 n,第x行 第一个 是 第 x-1个人可以给几个人报信,和时间 球最少时间 和从第几个人开始报信
水题,Floyd 一遍 过;
ME 676KB
TI 16MS
#include <iostream> #include <stdio.h> #include <stdlib.h> #include <math.h> #include <string.h> #include <algorithm> const int INF = 1e7; const int N = 105; using namespace std; int mapp[N][N],n; void init() { for(int i = 1;i<=n;i++) { for(int j = 1;j<=n;j++) { mapp[i][j] = INF; } } } void Floyd() { int k,j,i; for(k = 1;k<=n;k++) { for(i = 1;i<=n;i++) { for(j=1;j<=n;j++) { if(mapp[i][j] > mapp[i][k] + mapp[k][j]) mapp[i][j] = mapp[k][j] + mapp[i][k]; } } } } int main() { int s,wz,ti; while(scanf("%d",&n),n) { init(); for(int i = 1;i<=n;i++) { scanf("%d",&s); for(int j = 1;j<=s;j++) { scanf("%d%d",&wz,&ti); mapp[i][wz] = ti; } } Floyd(); int st = -1,maxx = 0,ti = INF; for(int i = 1;i<=n;i++) { maxx = 0; for(int j = 1;j<=n;j++) { if(i==j) continue; if(mapp[i][j]> maxx) { maxx = mapp[i][j]; } } if(ti>maxx) { ti = maxx; st = i; } } if(st!=-1) printf("%d %d\n",st,ti); else puts("disjoint"); } return 0; }
POJ 1125-Stockbroker Grapevine,布布扣,bubuko.com
POJ 1125-Stockbroker Grapevine
原文:http://blog.csdn.net/wjw0130/article/details/30542373