「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

Sample Output

建出来的图：

我们可以考虑把图分成 $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;
}