题目描述
在郊区有 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
(二分+01BFS)
详见算法竞赛进阶指南
算法2
(分层图最短路)
题目中,每个点都有两个决策方式:走下一条边,不走下一条边
而且是问最短路
于是我们就可以想到分层图最短路
把原图复制k份,对于(u,v)这条边,建立了(u+n,v+n),(u+2n,v+2n)......(u+(k-1)n,v+(k-1)n)这些新边
两层图之间,连边(u,v+n),(v,u+n),边权为0,表示跳过这一条边不走
然后直接跑一个最短路(spfa(好像要卡),dijkstra.....),最后答案就是dis[n+k*n]
这样的话可以保证每个点的决策被考虑到
时间复杂度分析:O(eloge)(dij)
C++ 代码
#include<bits/stdc++.h>
using namespace std;
#define loop(i,start,end) for(register int i=start;i<=end;++i)
#define anti_loop(i,start,end) for(register int i=start;i>=end;--i)
#define clean(arry,num) memset(arry,num,sizeof(arry))
#define ll long long
template<typename T>void read(T &x){
x=0;char r=getchar();T neg=1;
while(r>'9'||r<'0'){if(r=='-')neg=-1;r=getchar();}
while(r>='0'&&r<='9'){x=(x<<1)+(x<<3)+r-'0';r=getchar();}
x*=neg;
}
int n,m,k;
const int maxn=1000+10;
const int maxm=10000+10;
const int maxk=maxn;
struct node{
int e;
int w;
int nxt;
}edge[maxn*6*maxk];
int head[maxn*maxk];
int cnt=0;
inline void addl(int u,int v,int w){
edge[cnt].e=v;
edge[cnt].w=w;
edge[cnt].nxt=head[u];
head[u]=cnt++;
}
struct point{
int pos;
ll dis;
point():pos(0),dis(0){}
point(int pos,int dis):pos(pos),dis(dis){}
friend bool operator<(point a,point b){
return a.dis>b.dis;
}
};
priority_queue<point>q;
ll dis[maxn*maxk];
inline void dijkstra(){
clean(dis,0x7f);
dis[1]=0;
q.push(point(1,0));
while(!q.empty()){
point f=q.top();
q.pop();
for(int i=head[f.pos];i!=-1;i=edge[i].nxt){
int v=edge[i].e;
if(dis[v]>max(dis[f.pos],(ll)edge[i].w)){
dis[v]=max(dis[f.pos],(ll)edge[i].w);
q.push(point(v,dis[v]));
}
}
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("datain.txt","r",stdin);
#endif // ONLINE_JUDGE
clean(head,-1);
read(n);
read(m);
read(k);
loop(i,1,m){
int ui,vi,li;
read(ui);
read(vi);
read(li);
addl(ui,vi,li);
addl(vi,ui,li);
loop(j,1,k){
addl(ui+n*j,vi+n*j,li);
addl(vi+n*j,ui+n*j,li);
addl(ui+n*(j-1),vi+n*j,0);
addl(vi+n*(j-1),ui+n*j,0);
}
}
dijkstra();
if(dis[n+k*n]<0x7f7f7f7f)
printf("%lld\n",dis[n+k*n]);
else printf("-1\n");
return 0;
}