简单记录一下看题解得到的几条经验

// dijkstra 求 dist 数组
// 根据 dist[i] - dist[j] == g[i][j] 为边建有向图
// 在这个有向图上用 DP 找 0 点到 n-1 点的路线数量

class Solution {
private:
    static constexpr int mod = 1000000007;  // private

public:
    const int MOD = 1e9 + 7;
    int countPaths(int n, vector<vector<int>>& roads) {
        vector<vector<long long>> dist(n, vector<long long>(n, LLONG_MAX / 2));
        // 经验: `LLONG_MAX` 常数是在 `climits` 标头中定义的宏常数，用于获取 `long long int` 对象的最大值
        for (int i = 0; i < n; ++ i)
            dist[i][i] = 0;
        
        for (auto&& road: roads)
        {
            int x = road[0], y = road[1], z = road[2];
            dist[x][y] = z;
            dist[y][x] = z;
        }
        // 经验: C++ `auto &&` 知乎: https://zhuanlan.zhihu.com/p/25148592
        // 1. 当你想要拷贝range的元素时，使用for(auto x : range).
        // 2. 当你想要修改range的元素时，使用for(auto && x : range).
        // 3. 当你想要只读range的元素时，使用for(const auto & x : range).

        // dijkstra
        vector<int> used(n);  // 经验: C++ 中 vector<int> 可以当作 vector<bool> 用, 赋值时 `used[t] = true` 就行
        for (int _ = 0; _ < n; ++ _)  // 经验: C++ 中可以定义变量 `_`
        {
            int t = -1;
            for (int j = 0; j < n; ++ j)
                if (!used[j] && (t == -1 || dist[0][j] < dist[0][t])) t = j;
            used[t] = true;
            
            for (int j = 0; j < n; ++ j)
                dist[0][j] = min(dist[0][j], dist[0][t] + dist[t][j]);
        }

        // 建有向图
        vector<vector<int>> g(n);
        for (auto&& road: roads)
        {
            int x = road[0], y = road[1], z = road[2];
            if (dist[0][x] - dist[0][y] == z) g[y].push_back(x);
            if (dist[0][y] - dist[0][x] == z) g[x].push_back(y);
        }

        // dfs
        vector<int> f(n, -1);
        function<int(int)> dfs = [&] (int u)
        {
            if (u == n - 1) return 1;
            if (f[u] != -1) return f[u];

            f[u] = 0;
            for (auto v: g[u])
            {
                f[u] += dfs(v);
                while (f[u] >= MOD) f[u] -= MOD;
            }
            return f[u];
        };
        return dfs(0);
    }
};