思路与算法

先Dijkstra求起点最短距离d。对边u→v定义额外代价δ=d[u]+w-d[v]，其非负。路径长度与到当前点最短距离之差就是沿路δ之和，只需状态0和1。按额外代价从0到1，再按d递增处理顶点，累加边转移，最后输出终点两状态之和。

正确性说明

松弛性质保证δ≥0。δ=0时w>0意味着d[v]>d[u]，所以同一偏差层严格沿距离增加，不会漏掉尚未累加的路径；δ=1进入后一层，其余边不可能贡献最短或长1的路线。每条路线按末边唯一分解，计数无重无漏。

复杂度

图和数组初始化O(N+M)，Dijkstra O((N+M)log(N+M))，排序O(NlogN)、双层转移O(N+M)；空间O(N+M)。

易错点

重边代表不同道路，分别累加。远离起点的点不参与。中间计数饱和为1000000001，因最终合法答案≤10^9且所有贡献非负，饱和不会改变合法终点结果，也避免死支路计数溢出。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    int T;
    cin >> T;
    while (T--) {
        int n, m;
        cin >> n >> m;
        vector<vector<pair<int, int>>> g(n);
        while (m--) {
            int a, b, w;
            cin >> a >> b >> w;
            g[--a].push_back({--b, w});
        }
        int s, t;
        cin >> s >> t;
        --s;
        --t;
        vector<int> d(n, 1000000000);
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        d[s] = 0;
        pq.push({0, s});
        while (!pq.empty()) {
            auto z = pq.top();
            pq.pop();
            if (z.first != d[z.second])
                continue;
            for (auto e : g[z.second])
                if (d[e.first] > z.first + e.second) {
                    d[e.first] = z.first + e.second;
                    pq.push({d[e.first], e.first});
                }
        }
        vector<int> ord(n);
        iota(ord.begin(), ord.end(), 0);
        sort(ord.begin(), ord.end(), [&](int a, int b) {
            return d[a] < d[b];
        });
        vector<array<long long, 2>> c(n);
        for (auto &x : c)
            x = {0, 0};
        c[s][0] = 1;
        for (int k = 0; k < 2; k++)
            for (int u : ord)
                if (d[u] < 1000000000)
                    for (auto e : g[u]) {
                        int z = d[u] + e.second - d[e.first];
                        if (z >= 0 && k + z < 2)
                            c[e.first][k + z] = min(1000000001LL, c[e.first][k + z] + c[u][k]);
                    }
        cout << c[t][0] + c[t][1] << '\n';
    }
}