【题目来源】
洛谷：[P1948 USACO08JAN] Telephone Lines S - 洛谷
【题目描述】
多年以后，笨笨长大了，成为了电话线布置师。由于地震使得某市的电话线全部损坏，笨笨是负责接到震中市的负责人。该市周围分布着 \(n\)（\(1\le n\le10^3\)）根按 \(1\sim n\) 顺序编号的废弃的电话线杆，任意两根线杆之间没有电话线连接，一共有 \(p\)（\(1\le p\le10^4\)）对电话杆可以拉电话线。其他的由于地震使得无法连接。
第 \(i\) 对电线杆的两个端点分别是 \(a_i,b_i\)，它们的距离为 \(l_i\)（\(1\le l_i\le10^6\)）。数据中每对 \((a_i,b_i)\) 只出现一次。编号为 \(1\) 的电话杆已经接入了全国的电话网络，整个市的电话线全都连到了编号 \(n\) 的电话线杆上。也就是说，笨笨的任务仅仅是找一条将 \(1\) 号和 \(n\) 号电线杆连起来的路径，其余的电话杆并不一定要连入电话网络。
电信公司决定支援灾区免费为此市连接 \(k\) （\(1\le k\le p\)）对由笨笨指定的电话线杆，对于额外的那些电话线，需要为它们付费，总费用决定于其中最长的电话线的长度（每根电话线仅连接一对电话线杆）。如果需要连接的电话线杆不超过 \(k\) 对，那么支出为 \(0\)。
请你计算一下，将电话线引到震中市最少需要在电话线上花多少钱？
【输入】
输入文件的第一行包含三个数字 \(n,p,k\)。
第二行到第 \(p+1\) 行，每行分别都为三个整数 \(a_i,b_i,l_i\)。
【输出】
一个整数，表示该项工程的最小支出，如果不可能完成则输出 \(-1\)。
【输入样例】
5 7 1
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6
【输出样例】
4
【算法标签】
《洛谷 P1948 Telephone Lines》 #搜索# #图论# #二分# #广度优先搜索BFS# #最短路# #USACO# #NOI导刊# #2008#
【代码详解】
#include <bits/stdc++.h>
using namespace std;const int N = 1005; // 最大节点数
const int M = 20005; // 最大边数int n, m, k; // 节点数、边数、允许的边数限制
int h[N], e[M], ne[M], w[M], idx; // 邻接表存储图
deque<int> q; // 双端队列用于0-1 BFS
int dist[N]; // 存储从起点到各点的最短距离
bool st[N]; // 标记数组，记录节点是否被访问过/*** 添加边到邻接表* @param a 边的起点* @param b 边的终点* @param c 边的权重*/
void add(int a, int b, int c)
{e[idx] = b;w[idx] = c;ne[idx] = h[a];h[a] = idx++;
}/*** 检查是否存在路径满足条件* @param bound 当前检查的边界值* @return 是否存在满足条件的路径*/
bool check(int bound)
{memset(st, 0, sizeof st); // 初始化访问标记memset(dist, 0x3f, N * 4); // 初始化距离为无穷大dist[1] = 0; // 起点到自身距离为0q.push_back(1); // 起点入队while (q.size()) // 队列不为空时循环{int t = q.front(); // 取出队首节点q.pop_front(); // 弹出队首节点if (st[t]) continue; // 如果已访问则跳过st[t] = true; // 标记为已访问// 遍历所有邻接边for (int i = h[t]; i != -1; i = ne[i]){int j = e[i]; // 邻接节点int v = w[i] > bound; // 判断当前边权重是否超过bound// 松弛操作if (dist[j] > dist[t] + v){dist[j] = dist[t] + v; // 更新最短距离// 根据v的值决定插入队列前端还是后端if (!v) q.push_front(j);else q.push_back(j);}}}// 判断终点距离是否满足条件return dist[n] <= k;
}int main()
{cin >> n >> m >> k; // 输入节点数、边数、限制kmemset(h, -1, sizeof h); // 初始化邻接表// 输入所有边（无向图）while (m--){int a, b, c;cin >> a >> b >> c;add(a, b, c);add(b, a, c);}// 二分查找最小满足条件的boundint l = 0, r = 1e6 + 1;while (l < r){int mid = l + r >> 1; // 取中间值if (check(mid)) r = mid; // 如果满足条件则缩小右边界else l = mid + 1; // 否则增大左边界}// 处理无解情况if (r == 1e6 + 1) r = -1;cout << r << endl; // 输出结果return 0;
}
【运行结果】
5 7 1
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6
4