Poj 3662 Telephone Lines（最短路+二分）

思路：题目即为从连接1--n的边中找出一条最长的边，使得不多于k条边大于此边。则可以二分边长L（从0到边长最大值），求连接1--n的边中有多少条边的边长大于该边长：建立新图，将所有大于该边长的边权值设为1，其他边的权值为0，则求1->n的最短路即为连接1-->n的边中大于该边的边的个数，若其小于等于k则继续二分1---L-1，否则二分L+1---n。

#include<cstdio>#include<queue>#include<cstring>#include<iostream>#include<algorithm>#define debuusing namespace std;const int maxn=1000+50;const int maxm=20000+50;const int INF=0x3f3f3f3f;struct Node{    int u,v,w;};struct Edge{    int nt,to,w;};int n,m,k,tot;queue<int> q;Node e[maxm];int head[maxn];Edge edge[maxm];int dist[maxn],v[maxn];int mindist(int s){    memset(v,0,sizeof(v));    while(!q.empty()) q.pop();    for(int i=1; i<=n; i++) dist[i]=INF;    dist[s]=0,v[s]=1,q.push(s);    while(!q.empty())    {        int now=q.front();        q.pop(),v[now]=0;        for(int i=head[now]; ~i; i=edge[i].nt)        {            int nt=edge[i].to;            if(dist[nt]>dist[now]+edge[i].w)            {                dist[nt]=dist[now]+edge[i].w;                if(!v[nt])                {                    v[nt]=1;                    q.push(nt);                }            }        }    }}void addedge(int u,int v,int w){    edge[tot].to=v,edge[tot].w=w;    edge[tot].nt=head[u],head[u]=tot++;    edge[tot].to=u,edge[tot].w=w;    edge[tot].nt=head[v],head[v]=tot++;}void init(){    tot=0;    memset(head,-1,sizeof(head));}void build(int len){    init();    for(int i=0; i<m; i++)    {        if(e[i].w>len) addedge(e[i].u,e[i].v,1);        else addedge(e[i].u,e[i].v,0);    }}int check(int len){    mindist(1);    return dist[n]<=k;}int solve(int maxx){    int l=0,r=maxx,ans;    while(l<=r)    {        int mid=(l+r)>>1;        build(mid);        if(check(mid))        {            ans=mid;            r=mid-1;        }        else l=mid+1;    }    return ans;}int main(){#ifdef debug    freopen("in.in","r",stdin);#endif // debug    int maxx=-INF;    scanf("%d%d%d",&n,&m,&k);    init();    for(int i=0; i<m; i++)    {        scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);        addedge(e[i].u,e[i].v,e[i].w);        maxx=max(maxx,e[i].w);    }    mindist(1);    if(dist[n]>=INF) printf("-1/n");    else    {        printf("%d/n",solve(maxx));    }    return 0;}