分层图的题都很麻烦地要在 dijkstra 外面套个循环,其实可以不用。
以经典模板 [JLOI2011] 飞行路线 为例,给 DJ 的优先队列里面的点加一维状态 \(k\),\(f(u,k)\) 可以免费转移到 \(f(v,k+1)\),也可以付费转移到 \(f(v,k)\)。
相当于 DJ 里面同时 \(k\) 层图都在跑,正确性显然(要是怀疑哪里有问题,套用普通 DJ 的证明就行)。复杂度 \(O(k(n+m\log m))\)。
模板题代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 10005;
int n, m, K, S, T, dis[N][12], vis[N][12];
vector<pair<int, int>> g[N];
priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> q;
int main() {
ios::sync_with_stdio(false);
cin >> n >> m >> K >> S >> T;
for(int i = 1, a, b, c; i <= m; i++) {
cin >> a >> b >> c;
g[a].emplace_back(make_pair(b, c));
g[b].emplace_back(make_pair(a, c));
}
memset(dis, 0x3f, sizeof dis);
dis[S][0] = 0;
q.push(make_tuple(0, S, 0));
while(!q.empty()) {
auto [d, u, k] = q.top();
q.pop();
if(vis[u][k]) continue;
vis[u][k] = true;
for(auto [v, w] : g[u]) {
if(dis[v][k] > d + w) {
dis[v][k] = d + w;
q.push(make_tuple(dis[v][k], v, k));
}
if(k < K && dis[v][k + 1] > d) {
dis[v][k + 1] = d;
q.push(make_tuple(dis[v][k + 1], v, k + 1));
}
}
}
int ans = 1e9;
for(int i = 0; i <= K; i++)
ans = min(ans, dis[T][i]);
cout << ans << '\n';
return 0;
}
其实我今天刚学分层图,再来做道题吧。
P3119 [USACO15JAN]Grass Cownoisseur G:tajran 缩点之后就可以给权值取负把求最长路转化为求最短路,DJ 的时候分 \(f(u,0/1)\),\(f(u,0)\) 只能通过走逆向边的方法转移到 \(f(v,1)\) 即可。
标签:DJ,int,make,笔记,vis,分层,dis From: https://www.cnblogs.com/huaruoji/p/16775727.html