D - Network Installation
【题目来源】
AtCoder：D - Network Installation
【题目描述】
Takahashi is working as a network engineer at a telecommunications company and is in charge of planning the installation of fiber optic cables.
高桥在一家电信公司担任网络工程师，负责规划光纤电缆的安装。
There are \(N\) relay stations in the city, numbered from \(1\) to \(N\). There are also \(M\) underground tunnels, each connecting two different relay stations bidirectionally. The \(i\)-th tunnel \((1 \leq i \leq M)\) connects relay station \(U_i\) and relay station \(V_i\), and has a width of \(W_i\) centimeters.
该城市有 \(N\) 个中继站，编号从 \(1\) 到 \(N\)。还有 \(M\) 条地下隧道，每条隧道双向连接两个不同的中继站。第 \(i\) 条隧道（\(1 \leq i \leq M\)）连接中继站 \(U_i\) 和中继站 \(V_i\)，宽度为 \(W_i\) 厘米。
Takahashi wants to install a fiber optic cable bundle of width \(K\) centimeters from the data center at relay station \(1\) to the customer building at relay station \(N\). In order to pass the cable bundle through a tunnel, the width of that tunnel must be at least \(K\) centimeters. Therefore, all tunnels along the installation route must have a width of at least \(K\) centimeters.
高桥希望安装一条宽度为 \(K\) 厘米的光纤电缆束，从中继站 \(1\) 的数据中心连接到中继站 \(N\) 的客户大楼。为了让电缆束通过一条隧道，该隧道的宽度必须不小于 \(K\) 厘米。因此，安装路径上的所有隧道宽度都必须至少为 \(K\) 厘米。
Here, a path from relay station \(1\) to relay station \(N\) is a sequence of relay stations \(v_0, v_1, \ldots, v_L\) (\(L \geq 1\)) satisfying all of the following conditions:
这里，从中继站 \(1\) 到中继站 \(N\) 的一条路径是一个满足以下所有条件的中继站序列 \(v_0, v_1, \ldots, v_L\)（\(L \geq 1\)）：
- \(v_0 = 1\) and \(v_L = N\).
- For each \(j\) (\(1 \leq j \leq L\)), there exists a tunnel connecting relay station \(v_{j-1}\) and relay station \(v_j\).
对于每个 \(j\)（\(1 \leq j \leq L\)），存在一条隧道连接中继站 \(v_{j-1}\) 和中继站 \(v_j\)。 - \(v_0, v_1, \ldots, v_L\) are all distinct (no relay station is visited more than once).
\(v_0, v_1, \ldots, v_L\) 互不相同（不重复访问任何中继站）。
This path passes through \(L\) tunnels. We call this \(L\) the number of tunnels traversed by the path.
这条路径经过 \(L\) 条隧道。我们称 \(L\) 为该路径经过的隧道数量。
To reduce costs, Takahashi wants to minimize the number of tunnels traversed.
为了降低成本，高桥希望最小化经过的隧道数量。
Determine whether there exists a path where all tunnels along the path have a width of at least \(K\) centimeters. If such a path exists, output the minimum number of tunnels traversed among all such paths. If no such path exists, output -1.
判断是否存在一条路径，使得该路径上的所有隧道宽度都至少为 \(K\) 厘米。如果存在这样的路径，输出所有此类路径中经过的最小隧道数量。如果不存在这样的路径，输出 -1。
【输入】
\(N\) \(M\) \(K\)
\(U_1\) \(V_1\) \(W_1\)
\(U_2\) \(V_2\) \(W_2\)
\(\vdots\)
\(U_M\) \(V_M\) \(W_M\)
The first line contains the number of relay stations \(N\), the number of tunnels \(M\), and the width of the cable bundle \(K\) (in centimeters), separated by spaces.
The \(i\)-th of the following \(M\) lines \((1 \leq i \leq M)\) contains the numbers of the two relay stations \(U_i\), \(V_i\) connected by the \(i\)-th tunnel, and the width \(W_i\) (in centimeters) of that tunnel, separated by spaces.
【输出】
If there exists a path from relay station \(1\) to relay station \(N\) where all tunnels along the path have a width of at least \(K\) centimeters, output the minimum number of tunnels traversed among all such paths on a single line.
If no such path exists, output -1.
【输入样例】
5 6 5
1 2 3
1 3 7
2 5 10
3 4 6
4 5 8
1 5 2
【输出样例】
3
【代码详解】
#include <bits/stdc++.h>
using namespace std;
const int N = 200005, M = N * 2;int n, m, k;
// 邻接表存储图
int h[N], e[M], w[M], ne[M], idx;
int dist[N]; // 存储从起点到每个点的最短距离// 添加边
void add(int a, int b, int c)
{e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}// 广度优先搜索
void bfs()
{queue<int> q;memset(dist, -1, sizeof(dist)); // 初始化距离为-1表示未访问q.push(1);dist[1] = 0; // 起点到自己的距离为0while (!q.empty()){int u = q.front();q.pop();// 遍历u的所有邻接点for (int i = h[u]; i != -1; i = ne[i]){int v = e[i];// 如果v未被访问过if (dist[v] == -1){q.push(v);dist[v] = dist[u] + 1; // 更新距离}}}
}int main()
{cin >> n >> m >> k;memset(h, -1, sizeof(h)); // 初始化邻接表for (int i = 1; i <= m; i++){int u, v, w;cin >> u >> v >> w;// 只添加边权大于等于k的边if (w >= k){add(u, v, w), add(v, u, w);}}bfs(); // 从起点1开始BFScout << dist[n] << endl; // 输出起点到n点的最短距离return 0;
}
【运行结果】
5 6 5
1 2 3
1 3 7
2 5 10
3 4 6
4 5 8
1 5 2
3