POJ3662 Telephone Lines（SPFA+二分）

题意：

在无向图上求一条从1到N的路径，使得路径上第K+1大的边权尽可能小。

题解：

把大于等于mid的边权置为1，小于mid的边置为0，求1到N的最短路是否大于K，二分处理。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int maxn=1e6;
const int inf=1e9;
int N,M,K;
int head[maxn];
int tol;
struct node {
    int u;
    int v;
    int w;
    int next;
}edge[maxn];
void addedge (int u,int v,int w) {
    edge[tol].u=u;
    edge[tol].v=v;
    edge[tol].w=w;
    edge[tol].next=head[u];
    head[u]=tol++;
}
int d[maxn];
int visit[maxn];
int spfa (int s,int x) {
    //比x大的边置为1，比x小的边置为0 
    for (int i=1;i<=N;i++) d[i]=inf,visit[i]=0;
    d[s]=0;
    visit[s]=1;
    queue<int> q;
    q.push(s);
    while (!q.empty()) {
        int u=q.front();
        q.pop();
        visit[u]=0;
        for (int i=head[u];i!=-1;i=edge[i].next) {
            int v=edge[i].v;
            if (d[v]>d[u]+(edge[i].w>=x?1:0)) {
                d[v]=d[u]+(edge[i].w>=x?1:0);
                if (!visit[v]) q.push(v),visit[v]=1;
            }
        }
    }
    return d[N]>=K+1;
}

int main () {
    while (~scanf("%d%d%d",&N,&M,&K)) {
        memset(head,-1,sizeof(head));
        tol=0;
        for (int i=0;i<M;i++) {
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            addedge(u,v,w);
            addedge(v,u,w);
        }
        int l=0,r=1e6+10,ans=-1;
        while (l<=r) {
            int mid=(l+r)>>1;
            if (spfa(1,mid)) l=mid+1,ans=mid;
            else r=mid-1;
        }
        if (ans>1e6) ans=-1;
        if (r<0) ans=0;
        printf("%d
",ans);
    } 
    return 0;
}