传送门
题目大意： 你要把一个消息传给n个人， 这n个人中如果能传递消息则需要t时间。 求你应该先传达给谁能是的所有人都知道消息的时间最短。
题目分析： 又是一个求最短路， 不过是让所有节点的值得最大值最小。 每个节点都试一下即可， 求出每个节点开始时， 求出从这个节点出发， 所有节点的最大值。 保留最小的那个即可。
代码：
#include <iostream> #include <cstdio> #include <vector> #include <queue> #include <cstring> using namespace std; typedef pair<int, int> P; const int INF = 1 << 31 -1; int n; int mp[105][105]; int d[105]; priority_queue<P, vector<P>, greater<P> > que; int Dijkstra(int x) { bool used[105]; memset(used, false, sizeof(used)); fill(d, d+105, INF); d[x] = 0; que.push(P(0, x)); while(!que.empty()) { P p = que.top(); que.pop(); int v = p.second; if(d[v] < p.first) continue; used[v] = true; for(int i=1; i<=n; ++i) if(!used[i] && mp[v][i] != -1 && mp[v][i] + d[v] < d[i]) { d[i] = mp[v][i] + d[v]; que.push(P(d[i], i)); } } int ans = 0; for(int i=1; i<=n; ++i) ans = max(ans, d[i]); return ans; } int main() { while(scanf("%d", &n) && n) { memset(mp, -1, sizeof(mp)); for(int i=1; i<=n; ++i) { int x, v, w; scanf("%d", &x); for(int j=0; j<x; ++j) { scanf("%d%d", &v, &w); mp[i][v] = w; } } int ans = INF, num = 1, cur; for(int i=1; i<=n; ++i) { cur = Dijkstra(i); if(ans > cur) { num = i; ans = cur; } } printf("%d %d\n", num, ans); } return 0; }