CCC '15 S4 Convex Hull 题解

[原题传送门](https://dmoj.ca/problem/ccc15s4)

## 题意简述
题目非常清楚。

船从 $A$ 到 $B$，船体厚 $K$ 厘米。群岛有 $N$ 岛 $M$ 航线，每条航线连两岛，耗时 $t_i$、磨损 $h_i$。要找总磨损小于 $K$ 的最短耗时路线，到不了就输出 - 1。

即有 $N$ 个点，$M$ 条无向边，每条边都有权值 $t_i$ 和 $h_i$，求在 $h_i$ 的和小于 $K$ 时，从点 $A$ 到点 $B$ 的路径中 $t_i$ 的和的最小值。

## 思路分析

这道题可以用 BFS。

1. 最短路
2. 有约束条件（BFS 时可以检查，避免无效搜索）
3. 时间复杂度不会 TLE（不会超过 $O(n^2)$ ）

写起来有点繁琐，但是没有太大难度，代码中的 $dist_{i,j}$ 表示的是到达点 $i$ 、磨损度为 $j$ 时的最小 $t$ 的和（当然完全用结构体代替也是完全没有问题的）。

## 代码
代码如下：

```c
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 2e3 + 5, K = 200 + 5;

struct node
{
	int u, t, h;
};

struct node2
{
	int u, h;
};

vector <node> g[N];
int k, n, m, s, t, ans = 1e18, dist[N][K];
// k、n、m 的含义如题目
// s 同 A，t 同 B，分别表示起点终点
// ans 是最后的答案 
// dist[i][j] 表示到达点 i 、磨损度为 j 时的最小 t 的和

void bfs()
{
	queue <node2> q; // 队列中记录目前到达的点 u，和累计磨损度 h 
	memset (dist, -1, sizeof dist);
	dist[s][0] = 0;
	q.push({s, 0});
	// 初始化 & 入队 
	while (!q.empty())
	{
		int u = q.front().u, sumh = q.front().h; q.pop();
		for (auto nxt : g[u]) // 遍历接下来的点 
		{
			int v = nxt.u, nt = nxt.t, nh = nxt.h;
			if (sumh + nh >= k)	continue; // 如果磨损度超过 k，直接跳过 
			if (dist[v][sumh + nh] != -1 && dist[v][sumh + nh] <= dist[u][sumh] + nt)	continue; // 如果累加的 t 更小，也跳过 
			dist[v][sumh + nh] = dist[u][sumh] + nt;
			q.push({v, sumh + nh});
			// 否则更新、入队 
		}
	}
}

signed main()
{
	cin >> k >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int u, v, t, h;
		cin >> u >> v >> t >> h;
		// u、v 同题目中的 a、b 
		g[u].push_back({v, t, h});
		g[v].push_back({u, t, h});
		// 无向边两边都要存 
	}
	cin >> s >> t;
	bfs();
	for (int i = 0; i < k; i++)
		if (dist[t][i] != -1)	ans = min(ans, dist[t][i]);
	if (ans == (int)1e18)	cout << -1 << endl; // 记得判断 -1 的情况 
	else	cout << ans << endl;
	return 0;
}
```

正在渲染内容...