题解 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

#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;
}