做彩妆网站的公司,住房与城乡建设网上办事大厅,定制企业网站费用,陕西省建设部官方网站在郊区有 N 座通信基站#xff0c;P 条 双向 电缆#xff0c;第 i 条电缆连接基站 Ai 和 Bi。
特别地#xff0c;1 号基站是通信公司的总站#xff0c;N 号基站位于一座农场中。
现在#xff0c;农场主希望对通信线路进行升级#xff0c;其中升级第 i 条电缆需要花费 L…在郊区有 N 座通信基站P 条 双向 电缆第 i 条电缆连接基站 Ai 和 Bi。
特别地1 号基站是通信公司的总站N 号基站位于一座农场中。
现在农场主希望对通信线路进行升级其中升级第 i 条电缆需要花费 Li。
电话公司正在举行优惠活动。
农产主可以指定一条从 1 号基站到 N 号基站的路径并指定路径上不超过 K 条电缆由电话公司免费提供升级服务。
农场主只需要支付在该路径上剩余的电缆中升级价格最贵的那条电缆的花费即可。
求至少用多少钱可以完成升级。
输入格式
第 11 行三个整数 NPK
第 2..P12.. 行第 i1 行包含三个整数 Ai,Bi,Li
输出格式
包含一个整数表示最少花费。
若 11 号基站与 N 号基站之间不存在路径则输出 −1−1。
数据范围
0≤KN≤1000 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 解析
此题还可用最短路中的分层图解详情请看最短路分栏spfa分层图340. 通信线路《算法竞赛进阶指南》_Landing_on_Mars的博客-CSDN博客
详细思路请参考AcWing 340. 通信线路二分答案dijkstra - AcWing #includeiostream
#includecstdio
#includecstdlib
#includestring
#includecstring
#includecmath
#includectime
#includealgorithm
#includeutility
#includestack
#includequeue
#includevector
#includeset
#includemap
using namespace std;
typedef long long LL;
const int N 1e3 5;
int n, m, k;
vectorpairint, intG[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_queuest, vectorst, greaterstq;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].secondw?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,ans0,tt;while (lr) {mid l (r - l) / 2;tt dij(mid);if (tt 0x3f3f3f3f) {cout -1 endl;break;}if (tt) {r mid-1;}else {l mid1;ans mid;}}if (tt ! 0x3f3f3f3f)cout ans endl;return 0;
}
