POJ 3268 Silver Cow Party - SPFA 求雙向最短路最大值

問題描述

N ≤ 1000 個農場，M ≤ 100000 條單向路，每條路有耗時 T_i。派對在農場 X。每頭奶牛從所在農場去 X 再返回原農場，均選擇最短路徑。求所有奶牛往返耗時的最大值。

雙次 SPFA 解法

1. 建立原圖鄰接表，以 X 為源點跑 SPFA，得到 dist1[i] = i → X 的最短路？注意：原圖邊 u→v 表示從 u 到 v。奶牛從 i 去 X 是正向路徑，需在原圖上從 X 出發跑**反向圖**？更簡單：構建**反向圖**（邊 v→u），以 X 為源點跑 SPFA，得到的 dist_to_X[i] 即 i → X 的最短路。
2. 構建**原圖**，以 X 為源點跑 SPFA，得到 dist_from_X[i] 即 X → i 的最短路，即返回路徑 i ← X（原圖中 X→i）。
3. 答案 = max_{i≠X} (dist_to_X[i] + dist_from_X[i])。

SPFA 實現細節

• 隊列優化，inqueue 標記，計數器檢測負環（本題無負權）。
• 邊數組靜態分配 maxM*2。

複雜度

兩次 SPFA，平均 O(M)，最壞 O(NM) 但隨機圖極快。N=1000, M=100000 完全足夠。

參考代碼 (C++)

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int MAXN = 1010;
const int MAXM = 100010;
const int INF = 0x3f3f3f3f;

int head[MAXN], to[MAXM<<1], nxt[MAXM<<1], wgt[MAXM<<1], ecnt;
int dist[MAXN];
bool inq[MAXN];

void addEdge(int u, int v, int w) {
    to[ecnt] = v; wgt[ecnt] = w; nxt[ecnt] = head[u]; head[u] = ecnt++;
}

void spfa(int s, int n) {
    fill(dist, dist+n+1, INF);
    memset(inq, 0, sizeof(inq));
    queue<int> q;
    dist[s] = 0; q.push(s); inq[s] = true;
    while (!q.empty()) {
        int u = q.front(); q.pop(); inq[u] = false;
        for (int e = head[u]; e != -1; e = nxt[e]) {
            int v = to[e], w = wgt[e];
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                if (!inq[v]) { q.push(v); inq[v] = true; }
            }
        }
    }
}

int main() {
    int N, M, X;
    while (scanf("%d%d%d", &N, &M, &X) == 3) {
        memset(head, -1, sizeof(head)); ecnt = 0;
        static int U[MAXM], V[MAXM], W[MAXM];
        for (int i = 0; i < M; ++i) {
            scanf("%d%d%d", &U[i], &V[i], &W[i]);
        }
        // 反向圖：求 i -> X
        for (int i = 0; i < M; ++i) addEdge(V[i], U[i], W[i]);
        spfa(X, N);
        static int d1[MAXN];
        for (int i = 1; i <= N; ++i) d1[i] = dist[i];
        // 正向圖：求 X -> i
        memset(head, -1, sizeof(head)); ecnt = 0;
        for (int i = 0; i < M; ++i) addEdge(U[i], V[i], W[i]);
        spfa(X, N);
        int ans = 0;
        for (int i = 1; i <= N; ++i) if (i != X)
            ans = max(ans, d1[i] + dist[i]);
        printf("%d\n", ans);
    }
    return 0;
}