poj3662 二分+最短路

/*

给定一张无向图，要求找到1-n的路径，该路径上第k+1大的边是所有路径上最小的

如果没有1-n的路，那么输出-1

二分答案mid，遍历一次所有边，如果边权小于mid，则设为0，大于mid，则设为1

再求一次1-n的最短路，如果最短路大于k，则不成立，反之成立

*/

#include<iostream>

#include<cstring>

#include<cstdio>

#include<queue>

using namespace std;

#define maxn 1005

#define maxm 10005

struct Edge{int to,nxt,w,c;}edge[maxm<<];

int n,p,k,head[maxn],tot;

void init(){

    memset(head,-,sizeof head);

    tot=;

}

void addedge(int u,int v,int c){

    edge[tot].to=v;

    edge[tot].nxt=head[u];

    edge[tot].c=c;

    head[u]=tot++;

}

int d[maxn],v[maxn];

void dijkstra(){

    memset(d,0x3f,sizeof d);

    memset(v,,sizeof v);

    d[]=;

    priority_queue<pair<int,int> >q;

    q.push(make_pair(,));

    while(!q.empty()){

        int x=q.top().second;q.pop();

        if(v[x])continue;

        v[x]=;

        for(int i=head[x];i!=-;i=edge[i].nxt){

            int y=edge[i].to,z=edge[i].w;

            if(d[y]>d[x]+z){

                d[y]=d[x]+z;

                q.push(make_pair(-d[y],y));

            }

        }

    }

}

int judge(int mid){

    for(int x=;x<=n;x++)

        for(int i=head[x];i!=-;i=edge[i].nxt){

            if(edge[i].c<=mid)

                edge[i].w=;

            else edge[i].w=;

        }

    dijkstra();

    if(d[n]<=k)return ;

    return ;

}

int main(){

    while(cin>>n>>p>>k){

        init();

        for(int i=;i<=p;i++){

            int u,v,c;

            scanf("%d%d%d",&u,&v,&c);

            addedge(u,v,c);

            addedge(v,u,c);

        }

        int l=,r=,ans=-,mid;

        while(l<=r){

            mid=l+r>>;

            if(judge(mid))

                ans=mid,r=mid-;

            else l=mid+;

        }

        cout<<ans<<endl;

    }

}