前言
看到好多大佬都在跑分层图最短路，( ext{DP}) 解法的我瑟瑟发抖。。。
题目描述
给定一张 (N) 个点（点编号从 (0) 到 (N-1)），(M) 条边的无向带权图 (G)。给定常数 (k)，你可以在图 (G) 中使不超过 (k) 条边的边权为 (0)，求在该条件下点 (s) 到点 (t) 的最短路。
数据范围：(2le Nle10000,1le Mle50000,0le kle10)
基本思路
考虑 ( ext{DP})
我们设 (dis[i][u]) 表示从点 (s) 出发对 (i) 条边的边权清零时的最短路，答案就是 (dis[k][t])
考虑转移：
首先跑一遍裸的最短路，求出 (dis[0][u] u in[0,n-1])
然后对于 (forall i in [1,k])
[dis[i][u]=min{dis[i-1][v],dis[i][v]+(v,u)}
]
其中 (u) 是 (v) 的后继。
然后就可以开始转移了。
注意事项
- 点编号从 (0) 到 (N-1)
- 无向图边的空间开两倍
参考代码
/*--------------------------------
Author: The Ace Bee
Blog: www.cnblogs.com/zsbzsb
This code is made by The Ace Bee
--------------------------------*/
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <ctime>
#include <queue>
#define rg register
#define mp make_pair
#define pii pair < int, int >
using namespace std;
template < typename T > inline void read(T& s) {
s = 0; int f = 0; char c = getchar();
while (!isdigit(c)) f |= (c == '-'), c = getchar();
while (isdigit(c)) s = s * 10 + (c ^ 48), c = getchar();
s = f ? -s : s;
}
const int _ = 10010;
const int __ = 100010;
int n, m, k, s, t, dis[11][_], exi[_];
int tot, head[_], nxt[__], ver[__], w[__];
inline void Add_edge(int u, int v, int d)
{ nxt[++tot] = head[u], head[u] = tot, ver[tot] = v, w[tot] = d; }
queue < int > q1, q2;
inline void spfa1(int x) {
memset(dis[x], 0x3f, sizeof dis[x]);
dis[x][s] = 0, exi[s] = 1;
q1.push(s), q2.push(s);
while (!q1.empty()) {
int u = q1.front(); q1.pop(), exi[u] = 0;
for (rg int i = head[u]; i; i = nxt[i]) {
int v = ver[i];
if (dis[x][v] > dis[x - 1][u]) {
dis[x][v] = dis[x - 1][u];
if (!exi[v])
exi[v] = 1, q1.push(v), q2.push(v);
}
}
}
}
inline void spfa2(int x) {
if (x == 0)
memset(dis[x], 0x3f, sizeof dis[x]), q2.push(s);
dis[x][s] = 0, exi[s] = 1;
while (!q2.empty()) {
int u = q2.front(); q2.pop(), exi[u] = 0;
for (rg int i = head[u]; i; i = nxt[i]) {
int v = ver[i];
if (dis[x][v] > dis[x][u] + w[i]) {
dis[x][v] = dis[x][u] + w[i];
if (!exi[v]) exi[v] = 1, q2.push(v);
}
}
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.in", "r", stdin);
#endif
read(n), read(m), read(k), read(s), read(t);
for (rg int u, v, d, i = 1; i <= m; ++i)
read(u), read(v), read(d), Add_edge(u, v, d), Add_edge(v, u, d);
spfa2(0);
// for (rg int u = 0; u < n; ++u)
// printf("%d%c", dis[0][u], "
"[u == n - 1]);
for (rg int i = 1; i <= k; ++i) {
spfa1(i);
// for (rg int u = 0; u < n; ++u)
// printf("%d%c", dis[i][u], "
"[u == n - 1]);
spfa2(i);
// for (rg int u = 0; u < n; ++u)
// printf("%d%c", dis[i][u], "
"[u == n - 1]);
}
printf("%d
", dis[k][t]);
return 0;
}
完结撒花 (QwQ)