POJ3662电缆

题目：http://poj.org/problem?id=3662

二分答案。然后边权>mid的边的边权2记为1，否则记为0。找一个边权2的最短路，看dis[n]是否<=K。

别忘了不能到达要输出-1。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

#define ll long long

using namespace std;

const int N=,M=,INF=;

int n,m,head[N],xnt,dis[N],K;

ll l,r,ans;

bool vis[N];

struct Edge{

    int next,to;ll w;bool c;

    Edge(int n=,int t=,ll w=,bool c=):next(n),to(t),w(w),c(c) {}

}edge[M<<];

void add(int x,int y,int z)

{

    edge[++xnt]=Edge(head[x],y,z,);head[x]=xnt;

    edge[++xnt]=Edge(head[y],x,z,);head[y]=xnt;

}

bool dj()

{

    memset(dis,,sizeof dis);

    memset(vis,,sizeof vis);

    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;

    dis[]=;q.push(make_pair(,));

    while(q.size())

    {

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

        while(vis[k]&&q.size())k=q.top().second,q.pop();

        if(vis[k])break;vis[k]=;

        for(int i=head[k],v;i;i=edge[i].next)

            if(dis[k]+edge[i].c<dis[v=edge[i].to])

            {

                dis[v]=dis[k]+edge[i].c;q.push(make_pair(dis[v],v));

            }

    }

    return dis[n]<=K;

}

int main()

{

    scanf("%d%d%d",&n,&m,&K);int x,y;ll z;

    for(int i=;i<=m;i++)

    {

        scanf("%d%d%lld",&x,&y,&z);

        add(x,y,z);r=max(r,z);

    }

    while(l<=r)

    {

        ll mid=((l+r)>>);

        for(int i=;i<=xnt;i++)

        {

            if(edge[i].w>mid)edge[i].c=;

            else edge[i].c=;

        }

        if(dj())ans=mid,r=mid-;

        else l=mid+;

    }

    if(dis[n]==INF)ans=-;

    printf("%lld",ans);

    return ;

}