Silver Cow Party

poj3268.md

Poj 3268: Silver Cow Party

題目

分析

太巧妙了，只要做兩次 dijkstra 就可得到答案

---

題目要求所有牛前往 X，又從 X 回到它起點的最大時間（牛來回都走最短路徑）

可以分成前往 X、從 X 回來二個部份來看：

前往 X

前往 X 即是在求多起點，一終點的最短路徑……這相當於：

把所有邊反向，求一起點（X），多終點的最短路徑

於是就可以用 dijkstra 來做，dijkstra 產出的 d 陣列即為各點的牛前往 X 所花的最少時間

從 X 回來

不用說，一看就明瞭：

就是在原圖上做起點為 X 的最短路徑

用 dijkstra，其間產出的 d 陣列即為各點的牛從 X 回到各點的所花的最少時間

結論

將各隻牛前往 X、從 X 回來二部份的時間加起來，最大的時間和即為答案。

AC Code

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <functional>
#include <cstdio>
#include <cstring>
#include <cstdlib>

using namespace std;

struct Edge {
    int to, cost;
};

struct P {
    int v, dis;

    bool operator > (const P& p) const {
        return dis > p.dis;
    }
};

void dijkstra(const vector< vector<Edge> >& g, int S, vector<int>& d) {
    priority_queue< P, vector<P>, greater<P> > pq;
    fill(d.begin(), d.end(), 0x3f3f3f3f);

    pq.push(P{S, 0});
    d[S] = 0;

    while (!pq.empty()) {
        P p = pq.top(); pq.pop();
        // shouldn't use const P& p = pq.top();
        // since it's soon popped
        int v = p.v;

        if (p.dis > d[v]) // d[v] have been updated after p was added to pq
            continue;

        for (size_t i = 0; i < g[v].size(); i++) {
            const Edge& e = g[v][i];
            if (d[e.to] > d[v] + e.cost) {
                d[e.to] = d[v] + e.cost;
                pq.push(P{e.to, d[e.to]});
            }
        }
    }
}

int main() {
    int N, M, X;
    scanf("%d %d %d", &N, &M, &X);
    X--;

    vector< vector<Edge> > g(N);
    vector< vector<Edge> > rg(N);
    vector<int> d(N);
    vector<int> rd(N);

    for (int i = 0; i < M; i++) {
        int a, b, t;
        scanf("%d %d %d", &a, &b, &t);
        a--; b--;

        g[a].push_back(Edge{b, t});
        rg[b].push_back(Edge{a, t});
    }

    dijkstra(rg, X, rd); // go to X
    dijkstra(g, X, d); // back from X

    int ans = -1;
    for (int i = 0; i < N; i++) {
        int distance = rd[i] + d[i];
        if (distance > ans)
            ans = distance;
    }

    printf("%d\n", ans);

    return 0;
}