POJ-1125 Stockbroker Grapevine 最短路

本文转载自 Lyush 查看原文 2012/09/27 37 最短路/ poj

这题要处理的地方的就是一个人可以同时向多个人传递消息，也就是说一条消息的传递时间由最长的那一条路径所决定，因为可以同时进行嘛，所以就求某一点到所有点的最短路，然后再寻找一条最长的路劲，枚举每个顶点作为起点就可以了。

代码如下：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#include<cstring>
#include<vector>
#include<string>
#define inf 0x3f3f3f3f
#define LL long long
using 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;
}