本文共 1353 字，大约阅读时间需要 4 分钟。
这题要处理的地方的就是一个人可以同时向多个人传递消息，也就是说一条消息的传递时间由最长的那一条路径所决定，因为可以同时进行嘛，所以就求某一点到所有点的最短路，然后再寻找一条最长的路劲，枚举每个顶点作为起点就可以了。
代码如下：
#include #include #include #include #include #include #include #include #include #include #include #define inf 0x3f3f3f3f#define LL long longusing namespace std;int N, G[105][105], dis[105], vis[105];bool Dijkstra(int s, int &ret) { int pos, Min; ret = 0; memset(dis, 0x3f, sizeof (dis)); memset(vis, 0, sizeof (vis)); dis[s] = 0; for (int i = 1; i <= N; ++i) { Min = inf; for (int j = 1; j <= N; ++j) { if (!vis[j] && Min > dis[j]) { pos = j, Min = dis[j]; } } if (Min == inf) { return false; } else { vis[pos] = 1; for (int j = 1; j <= N; ++j) { if (!vis[j] && G[pos][j] != inf && dis[j] > dis[pos] + G[pos][j]) { dis[j] = dis[pos] + G[pos][j]; } } } } for (int i = 1; i <= N; ++i) { ret = max(ret, dis[i]); } return true;}int main(){ int a, b, M, flag, Min, num, ret; while (scanf("%d", &N), N) { flag = 0; Min = inf; memset(G, 0x3f, sizeof (G)); for (int i = 1; i <= N; ++i) { scanf("%d", &M); for (int j = 1; j <= M; ++j) { scanf("%d %d", &a, &b); G[i][a] = b; } } for (int i = 1; i <= N; ++i) { int t; if (Dijkstra(i, t)) { flag = 1; if (Min > t) { Min = t, num = i; } } } if (!flag) puts("disjoint"); else printf("%d %d\n", num, Min); } return 0;}
转载地址：http://guodx.baihongyu.com/