题目描述
在郊区有 N 座通信基站,P 条 双向 电缆,第 i 条电缆连接基站 Ai 和 Bi。
特别地,1 号基站是通信公司的总站,N 号基站位于一座农场中。
现在,农场主希望对通信线路进行升级,其中升级第 i 条电缆需要花费 Li。
电话公司正在举行优惠活动。
农产主可以指定一条从 1 号基站到 N 号基站的路径,并指定路径上不超过 K 条电缆,由电话公司免费提供升级服务。
农场主只需要支付在该路径上剩余的电缆中,升级价格最贵的那条电缆的花费即可。
求至少用多少钱可以完成升级。
输入格式
第 1 行:三个整数 N,P,K。
第 2..P+1 行:第 i+1 行包含三个整数 Ai,Bi,Li。
输出格式
包含一个整数表示最少花费。
若 1 号基站与 N 号基站之间不存在路径,则输出 −1。
数据范围
0≤K<N≤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
算法1
C++ 代码
#include<cstdio>
#include<bits/stdc++.h>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N = 1e5;
const int M = 1e3+ 10;
int head[N],idx = 0,dis[M][M],n,m,k,tot;
bool vis[M];
queue<int>q;
struct node{
int to;
int next;
int val;
}e[N];
void add(int u,int v,int w){
e[++idx].to = v;
e[idx].val = w;
e[idx].next = head[u];
head[u] = idx;
}
void spfa(int s){
memset(dis,0x3f,sizeof(dis));
memset(vis,false,sizeof(vis));
dis[s][0] = 0;
vis[s] = 1;
q.push(s);
while(q.size()){
int u = q.front();
q.pop();
vis[u] = false;
for(register int i = head[u]; i; i = e[i].next){
int v = e[i].to;
int z = e[i].val;
int w = max(dis[u][0],z);
if(dis[v][0] > w){
dis[v][0] = w;
if(!vis[v]){
vis[v] = true;
q.push(v);
}
}
for(register int p = 1;p <= k;p ++){
int w = min(dis[u][p - 1],max(dis[u][p],z));
if(dis[v][p] > w){
dis[v][p] = w;
if(!vis[v]){
vis[v] = true;
q.push(v);
}
}
}
}
}
}
int read(){
char c = getchar();
int f = 1,x = 0;
while(!isdigit(c)){if(c == '-') f = -1; c = getchar();}
while(isdigit(c)){x = (x << 1) + (x << 3) + (c - '0'); c = getchar();}
return x * f;
}
int main(){
n = read(),m = read(),k = read();
for(register int i = 1;i <= m;i ++){
int u,v,w;
u = read(),v = read(),w = read();
add(u,v,w);
add(v,u,w);
}
spfa(1);
int ans = 1e9;
for(int i = 0;i <= k;i ++){
ans = min(ans,dis[n][i]);
}
if(ans == 1e9) puts("-1");
else printf("%d",ans);
return 0;
}