<题目链接>
题目大意：
在一个节点标号为1~n的无向图中，求出一条1~n的路径，使得路径上的第K+1条边的边权最小。
解题分析：
直接考虑情况比较多，所以我们采用二分答案，先二分枚举第K+1条路的边权，然后根据枚举的边权，重新建图。因为john只需要支付除K条边之后权值最大的边，所以对于所有边权小于等于枚举边的，将其边权置为0，对于那些大于枚举边权的边，边权则置为1，这样，对1~n跑最短路，就能够用于判断枚举的答案是否成立。因为建的是边权为0、1的图求最短路，所以也可以用双端队列实现的BFS求解。
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;#define clr(a,b) memset(a,b,sizeof(a))
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define pb push_back
const int N = 1e3+, M = 1e4+;
const int INF = 0x3f3f3f3f;
int n,m,k,cnt,head[N],vis[N];
struct Edge{
int to,nxt,val;
}edge[M<<];struct Ege{ //记录下初始输入边的个数
int x,y,w;
Ege(int _x=,int _y=,int _w=):x(_x),y(_y),w(_w){}
};
vector<Ege>vec;struct Node{
int dist,loc;
Node(int _dist=,int _loc=):dist(_dist),loc(_loc){}
bool operator <(const Node &tmp)const{ return dist>tmp.dist; }
}node[N];void init(){
cnt=;clr(head,-);
}
void addedge(int u,int v,int w){
edge[++cnt].to=v,edge[cnt].val=w;
edge[cnt].nxt=head[u],head[u]=cnt;
}
void Getmap(int x){
init();
for(int i=;i<vec.size();i++){
Ege now=vec[i];
int u=now.x,v=now.y,w=now.w;
if(w<=x)addedge(u,v,),addedge(v,u,); //将花费<=k的道路边权置0，因为john只需要支付最大的道路
else addedge(u,v,),addedge(v,u,); //大于的边置为1,免费的k条边是否能够在满足题目条件的情况下，连通1~n点
}
}
bool check(int x){
Getmap(x); //根据枚举的答案，建立0、1图，然后在这个0、1图上跑最短路
priority_queue<Node>q;
for(int i=;i<=n;i++){
vis[i]=,node[i].loc=i,node[i].dist=INF;
}
node[].dist=;
q.push(node[]);
while(q.size()){
int u=q.top().loc;q.pop();
if(vis[u])continue;
vis[u]=;
for(int i=head[u];~i;i=edge[i].nxt){
int v=edge[i].to;
if(node[v].dist>node[u].dist+edge[i].val){
node[v].dist=node[u].dist+edge[i].val;
q.push(node[v]);
}
}
}
if(node[n].dist<=k)return true;
return false;
}
int main(){
while(scanf("%d%d%d",&n,&m,&k)!=EOF){
rep(i,,m){
int u,v,w;scanf("%d%d%d",&u,&v,&w);
vec.pb(Ege(u,v,w));
}
int l=,r=1e6+,ans=-;
while(l<=r){ //二分答案，枚举john需要支付的钱数,即连通1~n的道路中，除k条路外，花费最大的路径
int mid=l+r>>;
if(check(mid))ans=mid,r=mid-;
else l=mid+;
}
printf("%d\n",ans);
}
}
2019-03-06
