通信线路
在郊区有 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
#include<bits/stdc++.h>
using namespace std;
const int N=1000000+10,M=10000000+10;
typedef pair<int,int> PII;
int n,p,k;
int tot=0;
priority_queue<PII,vector<PII>,greater<PII> > q;
struct node
{
int ver,nex,edge;
}po[M];
int head[N],dis[N];
bool v[N];
void add(int x,int y,int z)
{
po[++tot].ver=y,po[tot].edge=z;
po[tot].nex=head[x],head[x]=tot;
}
void dijkstra()
{
memset(dis,0x3f,sizeof(dis));
dis[1]=0;
q.push(make_pair(0,1));
while(q.size())
{
int x=q.top().second;
q.pop();
if(v[x]) continue;
v[x]=true;
for(int i=head[x];i;i=po[i].nex)
{
int y=po[i].ver,z=max(po[i].edge,dis[x]);
if(dis[y]>z)
{
dis[y]=z;
q.push(make_pair(dis[y],y));
}
}
}
}
int main()
{
scanf("%d%d%d",&n,&p,&k);
for(int i=1,x,y,z;i<=p;i++)
{
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
add(y,x,z);
for(int j=1,z1=0;j<=k;j++)
{
add(x+(j-1)*n,y+j*n,z1);
add(y+(j-1)*n,x+j*n,z1);
add(x+j*n,y+j*n,z);
add(y+j*n,x+j*n,z);
}
}
for(int i=1,z=0;i<=k;i++)
add(i*n,(i+1)*n,z);
//如果读者认真观察代码的话一定会问为什么要有如此操作
//那么读者仔细思考，若无此操作，如果有一组数据 1 到 N 经过的边小于 k ，会发生什么呢？
dijkstra();
if(dis[(k+1)*n]==1061109567) puts("-1");
else printf("%d",dis[(k+1)*n]);
//感谢 Schelski 指出的错误：忘记判路径是否存在了。。。
return 0;
}