P9813 Convex Hull 题解

别样的阅读体验 / 别样的阅读体验

题目内容说的很直白了，接下来讲解做法。

思路

可以发现这是一个最短路问题，在最基础的模板上增加了一个“路径上边的 之和 ”的限制。

为方便讲解，我们将“路径上边的 之和”用一个字母 代替。

考虑仍然使用 Dijkstra 算法（堆优化），并且进行一些细微的改动。

首先， 数组要增加一维，即由 变成 ，同时，其定义变成 从起点到节点 ， 恰好为 的最短路径。

下面考虑对于算法实现过程的改动，具体表现为 更新 时的改动。

考虑当前点的“答案”，即当前点的 为某个小于 的值时距离起点的距离，是如何得到的。

可以类比一下 背包 的思想，会发现当前点的“答案”是通过相邻节点 对应位置 上的答案加上两点之间的距离转移来的。

那么什么是“对应位置”呢？

这个“位置”指的是下标，两点之间的下标应相差一个相应的 。

下面是形式化一些的表达：

假设当前的节点为 ，遍历到的相邻节点为 ，那么 更新 的方程为 ，其中 （ 不能小于 ，同时 要小于 ）。

直观地讲就是 下标 增加了一个 ，值 增加了一个 。（不难理解了吧……）

实现

#include <bits/stdc++.h>

using namespace std;

typedef pair <int, int> PII;

const int K = 210, N = 2e3 + 5, M = 1e4 + 5; // 数据范围

int k, n, m, s, t;
int he[N], tot;
struct edge {
	int to, nxt, t, h;
} e[M << 1]; // 双向边
int dis[N][K];
bool vis[N];
int ans = 0x3f3f3f3f; // 初始化成最大值，最终找到最小值

void add(int u, int v, int t, int h) {
	e[ ++ tot] = (edge) {v, he[u], t, h};
	he[u] = tot;
}

void dijkstra(int s) {
	memset(dis, 0x3f, sizeof dis); // 类似于普通的 Dijkstra 中的初始化
	dis[s][0] = 0;
	priority_queue <PII, vector <PII>, greater <PII> > q; // 小根堆
	q.push({0, s});
	while (q.size()) {
		auto p = q.top();
		q.pop();
		int u = p.second;
		for (int i = he[u]; i; i = e[i].nxt) {
			int v = e[i].to, h = e[i].h, t = e[i].t;
			int minn = 0x3f3f3f3f; // 要取一个“最小值”
			for (int j = 0; j < k - h; j ++ ) { // 循环区间合法
				if (dis[v][j + h] > dis[u][j] + t) {
					dis[v][j + h] = dis[u][j] + t;
					minn = min(minn, dis[v][j + h]); // 要在更新后的数据中找到“最小值”，以进行接下来的更新
				}
			}
			if (minn != 0x3f3f3f3f) // 如果“更新成功”
                q.push({minn, v}); // 那么就把“最小值”放进堆里，进行接下来的更新
		}
	}
}

int main() {
	cin >> k >> n >> m;
	for (int i = 1, u, v, t, h; i <= m; i ++ ) {
		cin >> u >> v >> t >> h;
		add(u, v, t, h), add(v, u, t, h); // 建双向边
	}
	cin >> s >> t;
	dijkstra(s); // 从起点开始
	for (int i = 0; i < k; i ++ ) ans = min(ans, dis[t][i]); // 在 p 所有小于 k 的答案中找最小值
	if (ans >= 0x3f3f3f3f / 2) // 一种技巧，即起点并不能通向终点，但终点会被其旁边的点更新
        puts("-1"); // 但是又不会变小太多，所以用正无穷的一半即可完成判定
	else  cout << ans << endl;
	return 0;
}