题意分析

题目要求计算吉米从办公室（节点$1$）到家（节点$2$）的不同“进步”路径数量。进步路径的定义是：从节点$A$到节点$B$的路径有效，当且仅当节点$B$到家的最短距离严格小于节点$A$到家的最短距离（即$dis[B] < dis[A]$）。

解题思路

1. 核心条件转化：

   • 定义$dis[u]$为节点$u$到家（节点$2$）的最短路径长度。
   • 路径$u \rightarrow v$是进步的，当且仅当$dis[v] < dis[u]$。

2. 算法步骤：

   • 反向最短路径：以家（节点$2$）为起点，使用Dijkstra算法计算所有节点到家的最短距离$dis[u]$。
   • 记忆化DFS：从办公室（节点$1$）出发，递归搜索所有满足$dis[v] < dis[u]$的后继节点$v$，并记录每个节点的路径数（避免重复计算）。

3. 状态设计：

   • path[u]表示从节点$u$到家的有效路径数，初始化为$-1$（未计算），递归终止条件为$u=2$时$path[u]=1$。

代码解释

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 1000 + 10;
const int INF = (1 << 30);
int Map[maxn][maxn], dis[maxn], path[maxn], m, n, vis[maxn];

// 初始化邻接矩阵
void init() {
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= n; j++)
            Map[i][j] = (i == j) ? 0 : INF;
}

// Dijkstra算法：计算从src到家的最短距离$dis[u]$
void Dijkstra(int src) {
    memset(vis, 0, sizeof(vis));
    for (int i = 0; i <= n; i++) dis[i] = Map[src][i];
    dis[src] = 0;
    
    for (int i = 1; i <= n; i++) {
        int minn = INF, pos = 0;
        for (int j = 1; j <= n; j++)
            if (!vis[j] && dis[j] < minn)
                minn = dis[pos = j];
        vis[pos] = 1;
        for (int j = 1; j <= n; j++)
            if (!vis[j] && dis[j] > dis[pos] + Map[pos][j])
                dis[j] = dis[pos] + Map[pos][j];
    }
}

// 记忆化搜索：计算从u到家的有效路径数
int dfs(int u) {
    if (path[u] != -1) return path[u];  // 直接返回已计算结果
    if (u == 2) return 1;  // 到达终点，路径数为1
    path[u] = 0;
    for (int v = 1; v <= n; v++)
        if (Map[u][v] != INF && dis[v] < dis[u])  // 满足进步条件$dis[v] < dis[u]$
            path[u] += dfs(v);
    return path[u];
}

int main() {
    while (scanf("%d", &n) && n) {
        scanf("%d", &m);
        init();
        for (int i = 0; i < m; i++) {
            int x, y, z;
            scanf("%d%d%d", &x, &y, &z);
            Map[x][y] = Map[y][x] = z;  // 双向边
        }
        Dijkstra(2);  // 计算所有节点到家的最短距离
        memset(path, -1, sizeof(path));  // 初始化记忆化数组
        printf("%d\n", dfs(1));  // 从节点1开始搜索
    }
    return 0;
}

注意事项

1. 反向Dijkstra：

   • 以家（节点$2$）为起点计算最短路径，因为进步条件是“后续节点到家的距离更短”，需要反向求解$dis[u]$。

2. 记忆化优化：

   • path[u]存储中间结果，避免重复计算，将时间复杂度从指数级降至线性级（每个节点和边仅访问一次）。

3. 进步条件判断：

   • 遍历节点$u$的所有邻接节点$v$，仅当存在边（$Map[u][v] \neq \text{INF}$）且$dis[v] < dis[u]$时，才计入路径数。

4. 数据范围：

   • 节点数$N \leq 1000$，邻接矩阵空间复杂度为$O(N^2)$，Dijkstra算法时间复杂度为$O(N^2)$，适合题目约束。

复杂度分析

• 时间复杂度：

  • Dijkstra算法：$O(N^2)$（节点数$N \leq 1000$，邻接矩阵实现）。
  • 记忆化DFS：$O(N+M)$（每个节点和边仅访问一次）。
    总体复杂度为$O(N^2)$，完全满足题目要求。

• 空间复杂度：

  • 邻接矩阵：$O(N^2)$。
  • 辅助数组（dis, path, vis）：$O(N)$。

该算法通过反向最短路径和记忆化搜索，高效地统计了所有符合“进步”条件的路径，确保了正确性和性能。