HDU 1142 森林漫步 — 最短路徑計數

問題重述：給定無向加權圖（節點 1 為辦公室，節點 2 為家），Jimmy 每天走不同路線回家，但要求每一步都「更接近家」：即從 A 走到 B 只有當 dist(B, 2) < dist(A, 2)。求從 1 到 2 滿足條件的路徑總數（保證 ≤ 2^31-1）。

解題思路

1. 反向 Dijkstra：以終點 2 為源點跑一次 Dijkstra，求出所有節點到 2 的最短距離 dist[u]。
2. 構建 DAG：對每條無向邊 (u, v, w)，若 dist[u] > dist[v] 則添加有向邊 u → v；若 dist[v] > dist[u] 則添加 v → u。這樣所有邊都指向「更近家」的方向，形成有向無環圖（DAG）。
3. 記憶化 DFS (DP)：在 DAG 上從 1 出發遞歸計數：dp[u] = Σ dp[v] for v in adj[u]，dp[2] = 1。利用 vis[u] 標記避免重複計算。

核心代碼（C++）

#include 
using namespace std;

const int MAXN = 1005;
const int INF = 0x3f3f3f3f;

struct Edge { int to, w; };
vector g[MAXN];
int dist[MAXN];
bool visDijk[MAXN];
int dp[MAXN];
bool visDp[MAXN];
int n, m;

void dijkstra(int src) {
    fill(dist, dist + n + 1, INF);
    fill(visDijk, visDijk + n + 1, false);
    priority_queue, vector>, greater>> pq;
    dist[src] = 0;
    pq.emplace(0, src);
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (visDijk[u]) continue;
        visDijk[u] = true;
        for (auto [v, w] : g[u]) {
            if (dist[v] > d + w) {
                dist[v] = d + w;
                pq.emplace(dist[v], v);
            }
        }
    }
}

int dfs(int u) {
    if (u == 2) return 1;
    if (visDp[u]) return dp[u];
    visDp[u] = true;
    int ans = 0;
    for (auto [v, w] : g[u]) {
        if (dist[u] > dist[v]) // 只走更近家的邊
            ans += dfs(v);
    }
    return dp[u] = ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    while (cin >> n, n) {
        cin >> m;
        for (int i = 1; i <= n; ++i) g[i].clear();
        for (int i = 0; i < m; ++i) {
            int a, b, d; cin >> a >> b >> d;
            g[a].push_back({b, d});
            g[b].push_back({a, d});
        }
        dijkstra(2); // 從家出發
        fill(visDp, visDp + n + 1, false);
        fill(dp, dp + n + 1, 0);
        cout << dfs(1) << '\n';
    }
    return 0;
}

複雜度分析

• Dijkstra：O(M log N)（堆優化），N ≤ 1000, M ≤ N*(N-1)/2。
• DFS：每節點訪問一次，O(N + M)。
• 總體極易通過 2 秒時限。

易錯點提示

1. 圖為無向圖，建圖時雙向添加邊。
2. Dijkstra 起點必須是 2（家），才能得到所有點到家的最短距離。
3. DFS 條件 dist[u] > dist[v] 嚴格對應「更接近家」。
4. 路徑數可能大，用 int（32 位有符號）足夠，題目保證 ≤ 2147483647。
5. 多測試用例，輸入以 0 結束。