题目链接

Silver Cow Party POJ - 3268

思路

$$ 正图反图跑两遍Dijkstra $$

时间复杂度

$$ O((E)log(V)) $$

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

const long long INF = 1e18;

class Dij {
public:

    typedef long long T;

    // .first = v
    // .second.first = w;
    // .second.second = next;
    vector<int> head;
    typedef pair<int, pair<T, int> > P;
    vector<P> e;
    int tot;
    vector<T> dist;


    inline void init(int cnt_n, int cnt_m) {
        head.resize(cnt_n + 5);
        dist.resize(cnt_n + 5);
        fill(head.begin(), head.end(), -1);
        e.resize(cnt_m * 2 + 10);
        tot = 0;
    }

    inline void add_edge(int u, int v, T w) {
        e[tot] = make_pair(v, make_pair(w, head[u]));
        head[u] = tot++;
    }

    inline void add_edges(int u, int v, T w) {
        add_edge(u, v, w);
        add_edge(v, u, w);
    }


    void gao(int s) {
        priority_queue<pair<T, int>
                 , vector<pair<T, int> >
                 , greater<pair<T, int> > > sm;
        fill(dist.begin(), dist.end(), INF);
        dist[s] = 0;
        sm.push(make_pair(0, s));

        while (!sm.empty()) {
            pair<T, int> p = sm.top();
            sm.pop();
            int u = p.second;
            if (dist[u] < p.first) {
                continue;
            }
            for (int i = head[u]; ~i; i = e[i].second.second) {
                int v = e[i].first;
                T w = e[i].second.first;
                if (dist[v] > dist[u] + w) {
                    dist[v] = dist[u] + w;
                    sm.push(make_pair(dist[v], v));
                }
            }
        }
    }
};

int main() {
    int n, m, s;
    scanf("%d%d%d", &n, &m, &s);// don't forget &
    Dij d1, d2;
    d1.init(n, m);
    d2.init(n, m);
    for (int i = 1; i <= m; i++) {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);// don't forget &
        d1.add_edge(x, y, z);
        d2.add_edge(y, x, z);
    }
    d1.gao(s);
    d2.gao(s);
    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        ans = max(ans, d1.dist[i] + d2.dist[i]);
    }
    printf("%lld", ans);
    return 0;
}