题解：P15716 [JAG 2023 Summer Camp #2] Drifting

· · 题解

要求 1 到 n 的最短路，但是给出 K 个三元组 (a,b,c)，要求走的时候不能连续经过 a,b,c，也就是不能在路径序列中有 a \to b \to c。

首先你注意到一个很隐蔽的事情，题目保证了 u_i<v_i，这说明图是一个 DAG。那么一条边一定不会被走两次。也可以自然的想到用类似拓扑排序上 dp 的方法求最短路。

因为有 K 的限制，因此在拓扑过程中需要记录下这个点的前驱 ls。而 u 的 ls 不同时，能转移到的点可能也不一样，所以要记下每个 u 由每个 ls 转移而来的最短路长度 dis。

现在将全部有用的信息记下来后，就可以自然的将 u 转移到 v 了。枚举 u 的每一个前驱，检查是否可以更新 v 的 dis。换句话说，就是将 u 所有合法的状态转移到 v。复杂度为 O(m^2)。

但是这样太慢了，原因也很简单。我们在每次转移到 v 的时候遍历了所有可行的 ls，但是其实我们只关心最小的那个合法的 dis。先对于 u 的 dis 排个序，那么第一个合法的就是最优的。不合法的次数只有 K 次，所有 u 的前驱数量和为 m，于是复杂度为 O(m\log m + n + K)。这里使用了 \operatorname{map} 实现，复杂度还要多一个 \log。

#include <bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define fi first
#define se second
#define pb emplace_back
#define mk make_pair
using namespace std;
typedef pair<int, int> pii;
const int N = 2e5 + 10, inf = 1e18, M = 2e6 + 10, mod = 1e9 + 7;
const double eps = 1e-8;
int n, m, head[N], ne[N << 1], to[N << 1], w[N << 1], id;
void add(int x, int y, int z) {
    to[++id] = y, ne[id] = head[x], head[x] = id, w[id] = z;
}
map<pair<pii, int>, bool> mp;
struct node { int u, dis, ls; };
int q[N], ql = 1, qr = 0, in[N];
vector<pii> dis[N];
void dijkstra() {
    for(int i = 1; i <= n; i++) {
        if(!in[i]) q[++qr] = i, dis[i].pb(mk((i == 1 ? 0 : inf), -1));
    }
    while(ql <= qr) {
        int u = q[ql++];
        sort(dis[u].begin(), dis[u].end());
        for(int i = head[u]; i; i = ne[i]) {
            int v = to[i]; in[v]--; 
            for(int j = 0; j < dis[u].size(); j++) {
                pii now = dis[u][j];
                if(mp.count(mk(mk(now.se, u), v))) continue;
                dis[v].pb(mk(now.fi + w[i], u));
                break;
            }
            if(!in[v]) q[++qr] = v;
        }
    }
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int x, y, z; cin >> x >> y >> z;
        add(x, y, z), in[y]++;
    }
    int K; cin >> K;
    for(int i = 1; i <= K; i++) {
        int x, y, z; cin >> x >> y >> z;
        mp[mk(mk(x, y), z)] = 1;
    }
    dijkstra();
    int mn = inf;
    for(auto now : dis[n]) mn = min(mn, now.fi);
    cout << (mn == inf ? -1 : mn) << "\n";
    return 0;
}