HDU 1142 森林漫步：Dijkstra + 記憶化搜索計數路徑

問題大意

給定無向加權圖（N≤1000 頂點，M 條邊），1 號點為辦公室，2 號點為家。從 1 走到 2，要求每一步必須「更接近終點」：即從 A 走到 B，需滿足 B 到 2 的最短路長度 < A 到 2 的最短路長度。求符合條件的不同路徑數。

解法思路

1. 逆向 Dijkstra：以 2 號點為源，計算所有點到 2 的最短距離 dis[i]。
2. 記憶化 DFS：從 1 號點出發，只能走向 dis[next] < dis[curr] 的鄰居。dp[u] 表示從 u 到 2 的合法路徑數，遞歸公式：dp[u] = Σ dp[v] (v 為滿足條件的鄰居)，邊界 dp[2]=1。
3. 拓撲序隱含在距離單調遞減中，無環，DFS 不會死循環。

AC 代碼

#include 
#include 
using namespace std;
const int maxn = 1005;
const int INF = 0x3f3f3f3f;

int n, m;
int a[maxn][maxn];
int dis[maxn];
bool vis[maxn];
int dp[maxn];

void Dijkstra(int src) {
    for (int i=1; i<=n; i++) dis[i] = a[src][i];
    memset(vis, 0, sizeof(vis));
    vis[src] = true; dis[src] = 0;
    for (int i=1; i> n, n) {
        cin >> m;
        memset(a, 0x3f, sizeof(a));
        for (int i=0; i> x >> y >> z;
            a[x][y] = a[y][x] = z;
        }
        Dijkstra(2);
        memset(dp, -1, sizeof(dp));
        dp[2] = 1;
        cout << DFS(1) << endl;
    }
    return 0;
}

鄰接矩陣存儲，Dijkstra O(N²) 適配 N≤1000。路徑數不超過 2147483647，int 足夠。