POJ 3268 Silver Cow Party：雙向 Dijkstra 求最大往返路徑

題目大意

給定一個有向帶權圖和一個點 S。每頭奶牛從各自節點出發去 S 聚會，聚會結束再返回。求所有奶牛往返路徑長度之和的最大值。即求 max(dist(u, S) + dist(S, u))。

解題策略

1. 正向圖：從 S 出發跑 Dijkstra，得到 `dist1[u]` = S 到 u 的最短路。
2. 反向圖：將所有邊反向，從 S 出發跑 Dijkstra，得到 `dist2[u]` = u 到 S 的最短路（等價於原圖中 u 到 S）。
3. 遍歷所有節點，計算 `dist1[u] + dist2[u]` 的最大值。

代碼實現 (C++)

#include 
#include 
#include 
#include 
using namespace std;

const int MAXN = 1010;
const int INF = 1 << 29;

struct Edge { int to, w; };
struct Node { int u, d; bool operator<(const Node& o) const { return d > o.d; } };

vector G[MAXN], GR[MAXN]; // 正向圖、反向圖
int dist1[MAXN], dist2[MAXN];
int n, m, s;

void dijkstra(int src, vector g[], int dist[]) {
    fill(dist + 1, dist + n + 1, INF);
    priority_queue pq;
    dist[src] = 0;
    pq.push({src, 0});
    while (!pq.empty()) {
        Node cur = pq.top(); pq.pop();
        if (cur.d > dist[cur.u]) continue;
        for (auto& e : g[cur.u]) {
            if (dist[e.to] > cur.d + e.w) {
                dist[e.to] = cur.d + e.w;
                pq.push({e.to, dist[e.to]});
            }
        }
    }
}

int main() {
    while (scanf("%d%d%d", &n, &m, &s) == 3) {
        for (int i = 1; i <= n; i++) { G[i].clear(); GR[i].clear(); }
        for (int i = 0; i < m; i++) {
            int u, v, w; scanf("%d%d%d", &u, &v, &w);
            G[u].push_back({v, w});
            GR[v].push_back({u, w}); // 反向邊
        }
        dijkstra(s, G, dist1);
        dijkstra(s, GR, dist2);
        int ans = 0;
        for (int i = 1; i <= n; i++) ans = max(ans, dist1[i] + dist2[i]);
        printf("%d\n", ans);
    }
    return 0;
}

複雜度分析

• 時間：O(M log N) 兩次 Dijkstra。
• 空間：O(N + M) 存圖。