二分，Dijkstra，340. 通信线路

340. 通信线路 - AcWing题库 

在郊区有 N 座通信基站，P 条 双向 电缆，第 i 条电缆连接基站 Ai 和 Bi。

特别地，1 号基站是通信公司的总站，N 号基站位于一座农场中。

现在，农场主希望对通信线路进行升级，其中升级第 i 条电缆需要花费 Li。

电话公司正在举行优惠活动。

农产主可以指定一条从 1 号基站到 N 号基站的路径，并指定路径上不超过 K 条电缆，由电话公司免费提供升级服务。

农场主只需要支付在该路径上剩余的电缆中，升级价格最贵的那条电缆的花费即可。

求至少用多少钱可以完成升级。

输入格式

第 1 行：三个整数 N，P，K

第 2..P+1 行：第 i+1 行包含三个整数 Ai,Bi,Li

输出格式

包含一个整数表示最少花费。

若 11 号基站与 N 号基站之间不存在路径，则输出 −1。

数据范围

0≤K 1≤P≤10000
1≤Li≤1000000

输入样例：

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

 解析：

 本题求的是：最大值的最小值 --> 二分（一般最大值的最小值都是使用二分来做）

 既然要使用二分来做，我们就需要寻找一个能使用二分来求解的性质，对其加以利用。

性质：从 1 ——N 是否存在一条路径，使得路径中 > mid 的边的个数 <= k 具有二段性。

因此可以对以上性质加以利用。

可以知道 >mid 的边应尽可能的少，所以我们可以使用最短路算法进行求解。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long LL;
const int N = 1e3 + 5;
int n, m, k;
vectorint, int>>G[N];
int d[N], v[N];
 
typedef struct st {
	int u, w;
}st;
 
bool operator>(const st& a, const st& b) {
	return a.w > b.w;
}
 
int dij(int w) {
	memset(d, 0x3f3f3f3f, sizeof(d));
	memset(v, 0, sizeof(v));
	priority_queue, greater>q;
	q.push({ 1,0 });
	d[1] = 0;
	int t;
	while (!q.empty()) {
		t = q.top().u;
		q.pop();
		if (v[t])
			continue;
		v[t] = 1;
		for (int i = 0; i < G[t].size(); i++) {
			int j = G[t][i].first, dist = G[t][i].second>w?1:0;
			if (d[j] > d[t] + dist) {
				d[j] = d[t] + dist;
				q.push({ j,d[j] });
			}
		}
	}
	if (d[n] == 0x3f3f3f3f)
		return d[n];
	return d[n] <= k;
}
 
int main() {
	cin >> n >> m >> k;
	for (int i = 1,a,b,t; i <= m; i++) {
		scanf("%d%d%d", &a, &b, &t);
		G[a].push_back({ b,t });
		G[b].push_back({ a,t });
	}
	int l = 0, r = 10, mid,ans=0,tt;
	while (l<=r) {
		mid = l + (r - l) / 2;
		 tt = dij(mid);
		if (tt == 0x3f3f3f3f) {
			cout << -1 << endl;
			break;
		}
		if (tt) {
			r = mid-1;
		}
		else {
			l = mid+1;
			ans = mid;
		}
	}
	if (tt != 0x3f3f3f3f)
		cout << ans << endl;
	return 0;
}

由上述分析可知，本题中的实际边权只有 0 和 1 ，因此我们还可以使用双端队列来处理。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef pair<double, int > PDI;
typedef pair<int, int> PII;
const int N = 1e3+5, M = 2e4 + 5;
int n, p, k;
int h[N], e[M], w[M], ne[M], idx;
int vis[N], d[N];
 
void add(int a, int b, int c) {
	e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
 
int check(int mid) {
	memset(vis, 0, sizeof vis);
	memset(d, 0x3f, sizeof d);
	deque<int>dq;
	d[1] = 0;
	dq.push_back(1);
	while (!dq.empty()) {
		int t = dq.front();
		dq.pop_front();
		if (t == n)break;
 
		if (vis[t])continue;
		vis[t] = 1;
		for (int i = h[t]; i != -1; i = ne[i]) {
			int j = e[i];
			int v = w[i] >= mid;
			if (d[j] > d[t] + v) {
				d[j] = d[t] + v;
				if (v) {
					dq.push_back(j);
				}
				else {
					dq.push_front(j);
				}
			}
		}
	}
	return d[n] <= k;
}
 
int main() {
	cin >> n >> p >> k;
 
	memset(h, -1, sizeof h);
 
	for (int i = 1,a,b,c; i <= p; i++) {
		scanf("%d%d%d", &a, &b, &c);
		add(a, b, c);
		add(b, a, c);
	}
	int l = 0, r = 1e6 + 5, mid, ret = 0;
	while (l <= r) {
		mid = l + (r - l) / 2;
		if (check(mid)) {
			r = mid - 1;
		}
		else {
			ret = mid;
			l = mid + 1;
		}
	}
 
	if (ret > 1e6) {
		cout << -1 << endl;
	}
	else {
		cout << ret << endl;
	}
 
	return 0;
}
 

 

（此题还可用最短路中的分层图解，详情请看最短路分栏spfa，分层图，340. 通信线路，《算法竞赛进阶指南》_Landing_on_Mars的博客-CSDN博客）