思路与算法

任意非支配路径都可去除环而不增费用和时间，因此费用只需考虑0至100(n-1)。把(城市,累计费用)作为状态，边权是旅行时间，用索引堆Dijkstra求每个状态的最短时间。最后按终点费用递增扫描，只在时间严格小于之前最小时间时计一个新种类。

正确性说明

非负费用/时间保证去环后的路径至少不差，故所有Pareto最优的不同费用时间对都可由简单路径实现，费用上界正确。扩展图与原路径费用累加一一对应，Dijkstra得到每个费用能实现的最短时间；同费用更长时间不可能非支配。递增费用扫描时，只有严格改善时间的点未被更便宜路径支配，相等时间也被支配，所以计数恰为不同Pareto种类。

复杂度

令C=100(n-1)，状态R=n(C+1)，扩展边O(mC)。时间O((R+mC)log R)，空间O(R+m)。索引堆每状态至多1个位置，避免重复堆条目失控；三个主要int数组及邻接表在64MiB内。距离数组与堆位置初始化O(R)，已计入。

易错点

同费用时间的不同路线只算一次。费用与时间可为0，不能用“每步都严格增”剪枝；零代价环也不制造新种类。无路输出0。独立答案枚举小图所有简单路径并精确过滤支配对，最大规模采用费用等于时间的图，只有一个最优种类。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
struct IndexedHeap {
    vector<int> h, pos;
    vector<int> &dist;
    IndexedHeap(int n, vector<int> &d) : pos(n, -1), dist(d) {
    }
    void swapAt(int a, int b) {
        swap(h[a], h[b]);
        pos[h[a]] = a;
        pos[h[b]] = b;
    }
    void decrease(int x) {
        int i = pos[x];
        if (i == -2)
            return;
        if (i == -1) {
            i = h.size();
            h.push_back(x);
            pos[x] = i;
        }
        while (i && dist[h[i]] < dist[h[(i - 1) / 2]]) {
            swapAt(i, (i - 1) / 2);
            i = (i - 1) / 2;
        }
    }
    int pop() {
        int ans = h[0];
        swapAt(0, h.size() - 1);
        h.pop_back();
        pos[ans] = -2;
        int i = 0;
        while (2 * i + 1 < (int)h.size()) {
            int j = 2 * i + 1;
            if (j + 1 < (int)h.size() && dist[h[j + 1]] < dist[h[j]])
                ++j;
            if (dist[h[i]] <= dist[h[j]])
                break;
            swapAt(i, j);
            i = j;
        }
        return ans;
    }
};
int main() {
    int n, m, s, t;
    cin >> n >> m >> s >> t;
    --s;
    --t;
    struct E {
        int v, c, w;
    };
    vector<vector<E>> g(n);
    for (int i = 0, a, b, c, w; i < m; ++i) {
        cin >> a >> b >> c >> w;
        --a;
        --b;
        g[a].push_back({b, c, w});
        g[b].push_back({a, c, w});
    }
    int cap = 100 * (n - 1), width = cap + 1, INF = 1000000000;
    vector<int> d(n * width, INF);
    IndexedHeap q(n * width, d);
    d[s * width] = 0;
    q.decrease(s * width);
    while (!q.h.empty()) {
        int id = q.pop(), u = id / width, c = id % width;
        for (auto e : g[u])
            if (c + e.c <= cap) {
                int next = e.v * width + c + e.c;
                if (d[next] > d[id] + e.w) {
                    d[next] = d[id] + e.w;
                    q.decrease(next);
                }
            }
    }
    int best = INF, answer = 0;
    for (int c = 0; c <= cap; ++c)
        if (d[t * width + c] < best) {
            best = d[t * width + c];
            ++answer;
        }
    cout << answer << '\n';
}