题意：
题目说明：
在郊区有N座通信基站，P条双向电缆，第i条电缆连接基站和
。特别地，1号基站是通信公司的总站，N号基站位于一座农场中，现在，农场主希望对通信线路进行升级，其中升级第i条电缆需要花费
(1 ≤
≤ 1,000,000)。
电话公司正在举行优惠活动。农场主可以指定一条从1号基站到N号基站的路径，并指定路径上不超过K条电缆，由电话公司免费提供升级服务。农场主可以指定一条从1号基站到N号基站的路径，并指定路径上不超过K条电缆，由电话公司免费提供升级服务。农场主只需要支付在该路径上剩余的电缆中，升级价格最贵的那条电缆的花费即可。求至少用多少钱能完成升级。
，
。
输入：
第1行：N P K
第2到P+1行： Ai, Bi, and Li
输出：
最少花费。如果不可能连接农场和公司总站，输出-1。
示例-输入数据：
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
提交地址：POJ3662
易错点：
- 将边权转化为0/1判定性问题.
#include<cstdio>
#include<iostream>
#include<queue>
using namespace std;
const int MAXN=1000010,MAXM=1000010,INF=2100000000;
int n;
struct Edge{
int from,to,w,nxt;
}e[MAXM];
int head[MAXN],edgeCnt=0;
void addEdge(int u,int v,int w){
e[++edgeCnt].from=u;
e[edgeCnt].to=v;
e[edgeCnt].w=w;
e[edgeCnt].nxt=head[u];
head[u]=edgeCnt;
}
int dis[MAXN],s;
struct Node{
int nowPoint,nowValue;
bool operator <(const Node &a)const{
return a.nowValue<nowValue;
}
};
int nowK=-1;//现在二分的值
int dijkstra(){
priority_queue<Node> q;
for(int i=1;i<=n;i++){
dis[i]=INF;
}
q.push(Node{s,0});dis[s]=0;
while(!q.empty()){
Node nowNode=q.top();q.pop();
int nowPoint=nowNode.nowPoint,nowValue=nowNode.nowValue;
if(dis[nowPoint]!=nowValue)continue;
for(int i=head[nowPoint];i;i=e[i].nxt){
int nowV=e[i].to;
int tmpW=e[i].w>nowK?1:0;
if(dis[nowV]>dis[nowPoint]+tmpW){
dis[nowV]=dis[nowPoint]+tmpW;
q.push(Node{nowV,dis[nowPoint]+tmpW});
}
}
}
return dis[n];
}
const int MAXL=1000005;
int main(){
int m,k;//边数和免费量
scanf("%d%d%d",&n,&m,&k);
s=1;
for(int i=1;i<=m;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
addEdge(u,v,w);
addEdge(v,u,w);
}
dijkstra();
int l=0,r=MAXL;
int ans=2000000001;
while(l<r){
int mid=(l+r)>>1;
nowK=mid;
if(dijkstra()>k)l=mid+1;
else r=mid;
}
if(l==MAXL){
printf("-1
");
}else printf("%d
",r);
return 0;
}