74 lines
2.5 KiB
C++
74 lines
2.5 KiB
C++
|
#include <bits/stdc++.h>
|
|||
|
|
using namespace std;
|
|||
|
|
typedef pair<int, int> PII;
|
|||
|
|
const int INF = 0x3f3f3f3f;
|
|||
|
|
const int N = 1010; // 1000个点
|
|||
|
|
const int M = 20010; // 10000条，记录无向边需要两倍空间
|
|||
|
|
int idx, h[N], e[M], w[M], ne[M];
|
|||
|
|
void add(int a, int b, int c) {
|
|||
|
|
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
|
|||
|
|
}
|
|||
|
|
int n; // 点数
|
|||
|
|
int m; // 边数
|
|||
|
|
|
|||
|
|
int k; // 不超过K条电缆，由电话公司免费提供升级服务
|
|||
|
|
|
|||
|
|
bool st[N]; // 记录是不是在队列中
|
|||
|
|
int dis[N]; // 记录最短距离
|
|||
|
|
|
|||
|
|
// mid指的是我们现在选最小花费
|
|||
|
|
bool check(int mid) {
|
|||
|
|
// 需要跑多次dijkstra，所以需要清空状态数组
|
|||
|
|
memset(st, false, sizeof st);
|
|||
|
|
memset(dis, 0x3f, sizeof dis);
|
|||
|
|
priority_queue<PII, vector<PII>, greater<PII>> q;
|
|||
|
|
dis[1] = 0;
|
|||
|
|
q.push({0, 1});
|
|||
|
|
|
|||
|
|
while (q.size()) {
|
|||
|
|
PII t = q.top();
|
|||
|
|
q.pop();
|
|||
|
|
int u = t.second;
|
|||
|
|
if (st[u]) continue;
|
|||
|
|
st[u] = true;
|
|||
|
|
for (int i = h[u]; ~i; i = ne[i]) {
|
|||
|
|
int j = e[i];
|
|||
|
|
int v = w[i] > mid; // 如果有边比我们现在选的这条边大，那么这条边对方案的贡献为1，反之为0
|
|||
|
|
if (dis[j] > dis[u] + v) {
|
|||
|
|
dis[j] = dis[u] + v;
|
|||
|
|
q.push({dis[j], j});
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
// 如果按上面的方法计算后，n结点没有被松弛操作修改距离，则表示n不可达
|
|||
|
|
if (dis[n] == INF) {
|
|||
|
|
puts("-1"); // 不可达，直接输出-1
|
|||
|
|
exit(0);
|
|||
|
|
}
|
|||
|
|
return dis[n] <= k; // 如果有k+1条边比我们现在这条边大，那么这个升级方案就是不合法的，反之就合法
|
|||
|
|
}
|
|||
|
|
int main() {
|
|||
|
|
memset(h, -1, sizeof h);
|
|||
|
|
cin >> n >> m >> k;
|
|||
|
|
int a, b, c;
|
|||
|
|
for (int i = 0; i < m; i++) {
|
|||
|
|
cin >> a >> b >> c;
|
|||
|
|
add(a, b, c), add(b, a, c);
|
|||
|
|
}
|
|||
|
|
/*
|
|||
|
|
这里二分的是直接面对答案设问： 至少用多少钱 可以完成升级
|
|||
|
|
依题意，最少花费其实是所有可能的路径中，第k+1条边的花费
|
|||
|
|
如果某条路径不存在k+1条边(边数小于k+1),此时花费为0
|
|||
|
|
同时，任意一条边的花费不会大于1e6,所以,这里二分枚举范围:0 ~ 1e6
|
|||
|
|
*/
|
|||
|
|
int l = 0, r = 1e6;
|
|||
|
|
while (l < r) {
|
|||
|
|
int mid = (l + r) >> 1;
|
|||
|
|
if (check(mid)) // check函数的意义：如果当前花费可以满足要求，那么尝试更小的花费
|
|||
|
|
r = mid;
|
|||
|
|
else
|
|||
|
|
l = mid + 1;
|
|||
|
|
}
|
|||
|
|
printf("%d\n", l);
|
|||
|
|
return 0;
|
|||
|
|
}
|