AcWing 340. 通信线路 - 二分答案 + SPFA
原题链接
中等
作者:
KeChang
,
2023-10-10 17:02:03
,
所有人可见
,
阅读 50
#include <iostream>
#include <queue>
#include <bitset>
#include <cstring>
using namespace std;
const int N = 1e3 + 10;
int g[N][N], n, m, k;
int check(int mid) {
int dist[N];
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
bitset <N> st;
st[1] = 1;
queue <int> que;
que.push(1);
while(que.size()) {
auto t = que.front(); que.pop();
st[t] = 0;
for (int i = 1; i <= n; ++i) {
if (g[t][i] != 0x3f3f3f3f) {
if(dist[i] > dist[t] + (g[t][i] > mid)) {
dist[i] = dist[t] + (g[t][i] > mid);
if (!st[i]) {
st[i] = 1;
que.push(i);
}
}
}
}
}
return dist[n];
}
int main () {
ios::sync_with_stdio(0);
cin.tie(0);
memset(g, 0x3f, sizeof g);
cin >> n >> m >> k;
for (int i = 0; i <= n; ++i) g[i][i] = 0;
int l = 0, r = 0;
while(m--) {
int a, b, c;
cin >> a >> b >> c;
r = max(r,c);
g[a][b] = g[b][a] = min(g[a][b], c);
}
while(l <= r) {
int mid = ((r - l) >> 1) + l, t = check(mid);
if (t == 0x3f3f3f3f) {
cout << -1;
return 0;
}
if (t > k) l = mid + 1;
else r = mid - 1;
}
cout << l;
return 0;
}