gyro永不抽风！ - Dijkstra
type: channel
link: https://gallery.gyrojeff.top/index.php/tag/Dijkstra/
items: P4568 [JLOI2011]飞行路线 - 三顾分层图最短路
items: 刷题计划 | 210902 | Dijkstra最短路

P4568 [JLOI2011]飞行路线 - 三顾分层图最短路
type: item
date: 2022-04-04T15:11:13+00:00
description: Preface 第三次做这题了... 顺便当成博客迁移了。下面的题解是高二上的时候写的，在 Hexo 的 blog，这里直接进行迁移：https://gyrojeff.moe/2020/09/18/P4568-JLOI2011-%E9%A3%9E%E8%A1%8C%E8%B7%AF%E7%BA%BF-%E5%88%86%E5%B1%82%E5%9B%BE%E6%9C%80%E7%9F%AD%E8%B7%AF/ 题面 https://www.luogu.com.cn/problem/P4568 题解 由于可以有$k$次免费，这里构建分层图： 有$k+1$层完全一样的图 每条边在层与层之间单向连接，但是费用为0 那么这样构建的图的第$i$层的$t$点就是免费了$i - 1$次的最小费用。 方程： $$ \text {ans} = \min _ {0 \leq i \leq k} \text {dis} [t_i] $$ 常见问题 如何防止从下面的层去上面？单向 如何建图？思考一下OpenCV当中的图像，其实他们的内存地址是连续的，所以我们可以把他们放在一个一维数组当中，只不过开了$n\times k$个点罢了。 图片（Ref @SuperJvRuo） 代码 #include <iostream> #include <queue> #include <cstring> #define int long long using namespace std; const int maxn = 1e4+5; const int maxm = 5e4+5; const int maxk = 15; struct edge { int next, to, w; } g[(maxm * maxk) << 2]; int head[maxn * maxk], dis[maxn * maxk], vis[maxn * maxk], ecnt = 2, n, m, k, s, t; void _add_edge(int u, int v, int w) { g[ecnt] = edge { head[u], v, w }; head[u] = ecnt ++; } void add_edge(int u, int v, int w) { _add_edge(u, v, w); _add_edge(v, u, w); } void add_edge(int u, int v, int k, int w) { add_edge(k * n + u, k * n + v, w); } void add_edge(int u, int v, int k1, int k2, int w) { _add_edge(k1 * n + u, k2 * n + v, w); _add_edge(k1 * n + v, k2 * n + u, w); } struct node { int pos, dis; friend bool operator < (const node &a, const node &b) { return a.dis > b.dis; } }; priority_queue<node> q; void dijkstra() { memset(dis, 0x7f, sizeof(dis)); dis[s] = 0; q.push(node { s, 0 }); while (!q.empty()) { int u = q.top().pos; q.pop(); if (vis[u]) continue; vis[u] = 1; for (int e = head[u]; e; e = g[e].next) { int v = g[e].to; if (vis[v]) continue; if (dis[v] > dis[u] + g[e].w) { dis[v] = dis[u] + g[e].w; q.push(node { v, dis[v] }); } } } } signed main() { cin >> n >> m >> k >> s >> t; while (m --> 0) { int u, v, w; cin >> u >> v >> w; for (int i = 0; i <= k; i ++) add_edge(u, v, i, w); for (int i = 0; i < k; i ++) add_edge(u, v, i, i + 1, 0); } dijkstra(); int ans = 8e18; for (int i = 0; i <= k; i ++) ans = min(ans, dis[t + i *…

刷题计划 | 210902 | Dijkstra最短路
type: item
date: 2021-09-03T01:41:00+00:00
description: Preface 之前做过很多最短路的题，基本上都使用堆优化的dijkstra，包括建立分层图等高级建图方法，但是一直没有系统地写过dijkstra本身是怎么推导的。今天重点想要形象地写一下以前金牌教练以前教最短路的方法。 单源最短路问题 我们先来简单地描述一下最短路问题：对于一张图 $G$，我们欲求起点 $S$ 到各点地最短距离。 要解决这个问题，我们不妨来先了解一下图论基本方程：对于每个点 $u$，记其到源点的最短距离为 $d(u)$，那么有如下表达： $$ d(u) = \min _ v \{ d(v) + w(v, u) \} $$ 上式中，$w(v, u)$ 为边 $(v, u)$ 的权。 定义这张图包含 $n + 1$ 个节点，除了源点记作 $S$ (或者 $u_0$)，其他点记作 $u_i$。 同时，在开始前，我们作如下规定： $$ w(u_i, u_i) = 0 $$ $$ (u, v) \notin G \Rightarrow w(u, v) = \infty $$ 现在，根据上面这个式子，我们不妨全部展开，便可以写出整张图的一张庞大的最短路表格： $$ \begin{aligned} &d(s) = 0 \\ &d(u_1) = \min \{ d(s) + w(s, u_1), d(u_1) + 0, d(u_2) + w(u_2, u_1), \cdots, d(u_n) + w(u_n, u_1)\} \\ &d(u_2) = \min \{ d(s) + w(s, u_2), d(u_1) + w(u_1, u_2), d(u_2) + 0, \cdots, d(u_n) + w(u_n, u_2)\} \\ &\cdots \\ &d(u_n) = \min \{ d(s) + w(s, u_n), d(u_1) + w(u_1, u_n), d(u_2) + w(u_2, u_n), \cdots , d(u_n) + 0 \} \end{aligned} $$ 对于如何求最短路，我们可以发现，其实这是一个 $n$ 元的方程组，我们需要做的便是解出这个方程组。 对于如何解这个方程，是一个有趣的问题。我们可以发现，等式的右边都是取最小值的 $\min$ 符号，这无疑大大增加了求解的难度。我们首先考虑一些简化的情况。 $$ \begin{aligned} a = \min \{ w_a', b + w_b, c + w_c \} \\ b = \min \{ w_b', a + w_a, c + w_c \} \\ c = \min \{ w_c', a + w_a, b + w_b \} \end{aligned} $$ 上式是一个简化的，除了源点外只有三个节点的情况，$w_a, w_b, w_c, w_a', w_b', w_c'$ 为定值，$a, b, c$ 为未知元。 我们有如下结论：形如上面这样的方程组，即右侧的待取最小的各项中所包含的未知元，也是其他方程的左侧待求值，那么，在所有待求最小值中的已经确定的值当中的最小值，必是那个方程的最小值。这么说可能非常抽象，所以我们不妨将上面的方程中代表常量的字母换成数字，来解释这个过程： $$ \begin{aligned} a = \min \{ 5, b + 5, c + 7 \} \\ b = \min \{ 7, a + 1, c + 6 \} \\ c = \min \{ 10, a + 4, b + 3 \} \end{aligned} $$ 在上面三个式子中，右侧的待求最小值中，只有 $5, 7, 10$ 是确定值，而这些确定值中 $5$ 是最小的，那么 $5$ 就是 $a$ 的值，我们将方程简化为： $$ \begin{aligned} &a = 5 \\ &b = \min \{ 7, 6, c + 6 \} = \min \{ 6, c + 6 \} \\ &c = \min \{ 10, 9, b + 3 \} = \min \{ 9, b + 3 \} \end{aligned} $$ 现在所有不定方程中的确定值为 $6, 9$，其中最小值为 $6$，所以 $b = 6$。 所以解得： $$ \begin{aligned} &a = 1 \\ &b = 6 \\ &c = \min \{ 9, 9 \} = 9 \end{aligned} $$ 总结一下我们上面的模拟： 我们每一次找到全局最小确定值 这个值所在的方程的未知数的解便是这个值 将这个值代入其他不定方程 化简其他不定方程，并将每个方程的若干定值项合并，我们便可以得到一个更小一阶的不定方程组。 接下来，我们不妨使用代数表达一下：设某个状态下简化过后的不定方程 $i$ 为…