题解 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)$ 的最短路。 ## Solution **分层图最短路** 模板题。 这类题目主要难在建图。 比如说，对于样例 ### Sample Input ``` 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 ``` 8 ``` 建出来的图：  我们可以考虑把图分成 $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 ```cpp #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; } ```