双调路径

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 2016 字
二维状态SPFA求费用时间帕累托前沿
一本通
例
正文

// 原题：https://oj.yecheng.tv/p/T1505
// 题意：n 点 m 条双向边各有费用 c 与时间 t，求 s 到 e 的「不被其它路径支配」的（费用,时间）对个数，同费用同时间只算一种。
// 思路：DP 出「花费恰好为 c 时到达各点的最少时间」，再在终点按费用从小到大扫一遍，时间是严格前缀最小的那些费用即为答案。
// 1. 费用和时间为非负，最优路径可取成简单路径，费用上界为 (n - 1) * 100 = 9900。
// 2. 状态为（点, 已花费用），用 SPFA 松弛最少时间。
// 复杂度：O(n * C * m) 时间 / O(n * C) 空间，C = 10000
// 易错点：道路是双向的，每条边要加两次。
// 易错点：支配关系是严格小于，费用更小但时间相等也算支配，所以前缀最小值相等时不能计数。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 105;
const int MAXC = 10000;
const int INF = 0x3f3f3f3f;
struct Edge{
    int to;
    int c;
    int t;
};
vector<Edge> g[MAXN];
int dis[MAXN][MAXC + 1];
bool inq[MAXN][MAXC + 1];
int main(){
    int n, m, s, e;
    if(!(cin >> n >> m >> s >> e)) return 0;
    for(int i = 0; i < m; i++){
        int p, r, c, t;
        cin >> p >> r >> c >> t;
        Edge a;
        a.to = r;
        a.c = c;
        a.t = t;
        g[p].push_back(a);
        Edge b;
        b.to = p;
        b.c = c;
        b.t = t;
        g[r].push_back(b);
    }
    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= MAXC; j++){
            dis[i][j] = INF;
        }
    }
    queue<pair<int, int> > q;
    dis[s][0] = 0;
    inq[s][0] = true;
    q.push(make_pair(s, 0));
    while(!q.empty()){
        int u = q.front().first;
        int c = q.front().second;
        q.pop();
        inq[u][c] = false;
        for(int i = 0; i < (int)g[u].size(); i++){
            int v = g[u][i].to;
            int nc = c + g[u][i].c;
            if(nc > MAXC) continue;
            int nt = dis[u][c] + g[u][i].t;
            if(dis[v][nc] > nt){
                dis[v][nc] = nt;
                if(!inq[v][nc]){
                    inq[v][nc] = true;
                    q.push(make_pair(v, nc));
                }
            }
        }
    }
    int best = INF;
    int ans = 0;
    for(int c = 0; c <= MAXC; c++){
        if(dis[e][c] >= INF) continue;
        if(dis[e][c] < best){
            best = dis[e][c];
            ans++;
        }
    }
    cout << ans << "\n";
    return 0;
}
双调路径

正文

一本通·提高篇的其它内容
