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

問題描述

N 個農場 (≤1000)，M 條單向道路 (≤100,000)，聚會地點 X。每隻奶牛從農場去 X 再返回，求所有奶牛往返路徑中最長的時間。

算法思路：雙向 Dijkstra

對於每個農場 i，需要：

• 去程：i → X 的最短路
• 回程：X → i 的最短路
• 總時間 = 去程 + 回程

直接對每個點跑 Dijkstra 太慢。關鍵觀察：

• 去程：在反向圖上從 X 出發跑一次 Dijkstra，得到所有點到 X 的距離
• 回程：在原圖上從 X 出發跑一次 Dijkstra，得到 X 到所有點的距離

代碼實現

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAX = 1007;
const int INF = 0x7fffffff;

int n, m, x;
int cost[MAX][MAX];
bool used[MAX];
int mincost[MAX];
int sum[MAX];

void Dijkstra_Go() { // 反向圖：求所有點到 x 的距離
    for (int i = 1; i <= n; ++i) {
        used[i] = false;
        mincost[i] = cost[i][x]; // 反向邊：i -> x
    }
    for (int i = 1; i <= n; ++i) {
        int k = -1, temp = INF;
        for (int j = 1; j <= n; ++j)
            if (!used[j] && mincost[j] < temp) { temp = mincost[j]; k = j; }
        if (k == -1) break;
        used[k] = true;
        for (int j = 1; j <= n; ++j)
            if (!used[j]) mincost[j] = min(mincost[j], mincost[k] + cost[j][k]);
    }
}

void Dijkstra_Back() { // 原圖：求 x 到所有點的距離
    for (int i = 1; i <= n; ++i) {
        used[i] = false;
        mincost[i] = cost[x][i];
    }
    for (int i = 1; i <= n; ++i) {
        int k = -1, temp = INF;
        for (int j = 1; j <= n; ++j)
            if (!used[j] && mincost[j] < temp) { temp = mincost[j]; k = j; }
        if (k == -1) break;
        used[k] = true;
        for (int j = 1; j <= n; ++j)
            if (!used[j]) mincost[j] = min(mincost[j], mincost[k] + cost[k][j]);
    }
}

int main() {
    while (~scanf("%d%d%d", &n, &m, &x)) {
        memset(sum, 0, sizeof(sum));
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                cost[i][j] = (i == j) ? 0 : INF;
        for (int i = 1; i <= m; ++i) {
            int a, b, c; scanf("%d%d%d", &a, &b, &c);
            cost[a][b] = c;
        }
        Dijkstra_Go();
        for (int i = 1; i <= n; ++i) sum[i] = mincost[i];
        Dijkstra_Back();
        for (int i = 1; i <= n; ++i) sum[i] += mincost[i];
        int ans = 0;
        for (int i = 1; i <= n; ++i) ans = max(ans, sum[i]);
        printf("%d\n", ans);
    }
    return 0;
}

複雜度分析

• 時間：O(N²) 兩次 Dijkstra，N=1000 完全可接受
• 空間：O(N²) 鄰接矩陣，也可用鄰接表優化至 O(M)
• 雙向策略將 N 次單源最短路降為 2 次，關鍵優化