Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
笨办法#include <stdio.h> #define MAX 100 #define INF 0x0fffffff int d[MAX + 1][MAX + 1]; int main() { int st_n, t, k, s, pair, id, dur, min, tmp, stat; while (1) { scanf("%d", &st_n); if (st_n == 0) break; for (t = 1; t <= st_n; ++t) for (k = 1; k <= st_n; ++k) { d[t][k] = INF; } for (t = 1; t <= st_n; ++t) d[t][t] = 0; for (t = 1; t <= st_n; ++t) { scanf("%d", &pair); for (k = 0; k < pair; ++k) { scanf("%d%d", &id, &dur); d[t][id] = dur; } } stat = 1; while (stat) { stat = 0; for (t = 1; t <= st_n; ++t) { for (k = 1; k <= st_n; ++k) { if (t != k) { for (s = 1; s <= st_n; ++s) { tmp = d[t][s] + d[s][k]; if (tmp < d[t][k]) { d[t][k] = tmp; stat = 1; } } } } } } min = INF; for (t = 1; t <= st_n; ++t) { tmp = 0; for (k = 1; k <= st_n; ++k) { if (d[t][k] > tmp) tmp = d[t][k]; } if (tmp < min) { min = tmp; id = t; } } if (min == INF) printf("disjoint\n"); else printf("%d %d\n", id, min); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator