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<<1]; int n,p,k,head[maxn],tot; void init(){ memset(head,-1,sizeof head); tot=0; } 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,0,sizeof v); d[1]=0; priority_queue<pair<int,int> >q; q.push(make_pair(0,1)); while(!q.empty()){ int x=q.top().second;q.pop(); if(v[x])continue; v[x]=1; for(int i=head[x];i!=-1;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[x],y)); } } } } int judge(int mid){ for(int x=1;x<=n;x++) for(int i=head[x];i!=-1;i=edge[i].nxt){ if(edge[i].c<=mid) edge[i].w=0; else edge[i].w=1; } dijkstra(); if(d[n]<=k)return 1; return 0; } int main(){ while(cin>>n>>p>>k){ init(); for(int i=1;i<=p;i++){ int u,v,c; scanf("%d%d%d",&u,&v,&c); addedge(u,v,c); addedge(v,u,c); } int l=0,r=1000005,ans=-1,mid; while(l<=r){ mid=l+r>>1; if(judge(mid)) ans=mid,r=mid-1; else l=mid+1; } cout<<ans<<endl; } }

 

转载于:https://www.cnblogs.com/zsben991126/p/10468143.html