「Luogu P4568」「JLOI2011」飞行路线

Description

给定一个 $n\ (2 \leq n \leq 10^4)$ 个点(编号为 $0 \sim n - 1$),$m\ (1 \leq m \leq 5 \times 10^4)$ 条边的无向图,其中最多可以把 $k\ (0 \leq k \leq 10)$ 条边的边权变成 $0$,求 $s$ 到 $t\ (0 \leq s,t < n)$ 的最短路。

Source

[Luogu]P4568

Solution

分层图最短路 模板题。

这类题目主要难在建图。

比如说,对于样例

Sample Input

1
2
3
4
5
6
7
8
5 6 1
0 4
0 1 5
1 2 5
2 3 5
3 4 5
2 3 3
0 2 100

Sample Output

1
8

建出来的图:

E8gzgs.png

我们可以考虑把图分成 $k + 1$ 层,每往下一层,边权变成 $0$ 的边就增加 $1$ 条。编号为 $i$ 的点在第 $j$ 层的编号为 $i + j \times n\ (0 \leq i < n,0 \leq j \leq k)$ 。

每一层都有同样的 $n$ 个点,$m$ 条边。

在层与层之间有单向边,边权为 $0$,且不能从下层到上层。

对于一条边权为 $w$ 的无向边 $u \leftrightarrow v$,我们可以在第 $i = 0 \sim k$ 层连无向边 $u + i \times n \leftrightarrow v + i \times n$,边权为 $w$,表示每一层里的 $u$ 和 $v$ 能互相到达,且花费的代价为 $w$ 。

紧接着,在第 $i - 1$ 层和第 $i$ 层之间连两条边权为 $0$ 的有向边 $u + (i-1) \times n \to v + i \times n$ 和 $v + (i-1) \times n \to u + i \times n$,表示可以把边 $u \to v$ 或 $v \to u$ 的边权变成 $0$,然后到下一层的 $v$ 点或 $u$ 点。

建图后,$s$ 到 $t + k \times n$ 的最短路即是用完 $k$ 次机会的最少花费。

最后可能没有用完 $k$ 次机会,所以到每层终点的最短路都有可能成为答案,取最小值即可。时间复杂度为 $O\left(mk\log (nk) \right)$ 。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

template <class T>
inline void read(T &x) {
x = 0;
char c = getchar();
bool f = 0;
for (; !isdigit(c); c = getchar()) f ^= c == '-';
for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
x = f ? -x : x;
}

template <class T>
inline void write(T x) {
if (x < 0) {
putchar('-');
x = -x;
}
T y = 1;
int len = 1;
for (; y <= x / 10; y *= 10) ++len;
for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}

const int MAXN = 2e5, MAXM = 5e6;
int n, m, k, s, t, tot, ans = 0x7fffffff, head[MAXN + 5], dis[MAXN + 5];
bool vis[MAXN + 5];
struct Edge {
int next, to, dis;
} e[MAXM + 5];
struct Node {
int val, id;
inline friend bool operator<(Node x, Node y) {
return x.val > y.val;
}
};

inline void addEdge(int u, int v, int w) {
e[++tot] = (Edge) { head[u], v, w };
head[u] = tot;
}

inline void dijkstra(int s) {//堆优化 dijkstra
memset(dis, 0x3f, sizeof (dis));
priority_queue<Node> q;
dis[s] = 0;
q.push((Node) { 0, s });
for (; !q.empty(); ) {
int u = q.top().id;
q.pop();
if (vis[u]) continue;
vis[u] = 1;
for (int v, w, i = head[u]; v = e[i].to, w = e[i].dis, i; i = e[i].next)
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
if (!vis[v]) q.push((Node) { dis[v], v });
}
}
}

int main() {
read(n), read(m), read(k), read(s), read(t);
++s, ++t;//点的编号改为 1 ~ n
for (int u, v, w, i = 1; i <= m; ++i) {
read(u), read(v), read(w);
++u, ++v;
addEdge(u, v, w), addEdge(v, u, w);
for (int j = 1; j <= k; ++j) {//一共 k 层
addEdge(u + (j - 1) * n, v + j * n, 0), addEdge(v + (j - 1) * n, u + j * n, 0);
//层与层之间对应的点连一条权值为 0 的边
addEdge(u + j * n, v + j * n, w), addEdge(v + j * n, u + j * n, w);
//每一层中对应的点连边
}
}
dijkstra(s);
for (int i = 0; i <= k; ++i) ans = min(ans, dis[t + i * n]);
//可能没有用完 k 次机会,所以要取 到每一层终点最短路 的最小值
write(ans);
putchar('\n');
return 0;
}

本文标题:「Luogu P4568」「JLOI2011」飞行路线

文章作者:Heartlessly

发布时间:2019年04月30日 - 10:46:14

最后更新:2019年04月30日 - 14:33:17

原始链接:https://heartlessly.github.io/problems/luogu-p4568/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

0%