UVA 10917 Walk Through the Forest：Dijkstra + DAG DP 計數路徑

問題描述

給定無向圖，起點 1，終點 2。只允許走滿足條件的邊 (A, B)：從 B 到終點的最短路長度 嚴格小於 從 A 到終點的最短路長度。求從 1 到 2 的合法路徑條數。

解題思路

1. 逆向 Dijkstra：從終點 2 出發跑 Dijkstra，得到每個點 d[u] 到終點的最短距離。
2. 構建 DAG：對原圖每條無向邊 (u, v)，若 d[v] < d[u] 則添加有向邊 u -> v；若 d[u] < d[v] 則添加 v -> u。若相等則不加（不滿足嚴格小於）。新圖必為 DAG（按 d 遞減拓撲有序）。
3. DAG 上 DP 計數路徑：dp[u] 為從 u 到 2 的路徑數。dp[2] = 1。按 d 從小到大（或 DFS 記憶化）遞推：dp[u] = Σ dp[v] 對所有 u -> v。答案為 dp[1]。

關鍵代碼結構

struct Edge { int from, to, dist; };
struct Dijkstra {
    vector edges;
    vector G[maxn];
    int d[maxn], n;
    void dijkstra(int s) {
        priority_queue Q;
        fill(d, d+n, INF); d[s]=0;
        Q.push({0,s});
        while(!Q.empty()) { ... }
    }
    ll dp[maxn];
    ll DP(int u) {
        if (u == 1) return 1; // 終點為1? 題目起點1終點2，此處DP(1)為答案
        if (dp[u] != -1) return dp[u];
        dp[u] = 0;
        for (int i : G[u]) {
            Edge &e = edges[i];
            if (d[e.to] < d[u]) dp[u] += DP(e.to);
        }
        return dp[u];
    }
};

注意事項

• 圖可能不連通，Dijkstra 需處理不可達點（d = INF）。
• 路徑數可能很大，用 long long（題目未要求取模）。
• 遞歸深度可能達 n，可改用拓撲序迭代 DP 避免棧溢出。