题目连接：http://poj.org/problem?id=3662
题意：有n个节点p条无向边，现在可以选择其中的任意K条免费，则花费为除了k条边后权值最大的一个，求最小花费多少。
分析：二分枚举最大边长limit，如果图中的边大于limit,则将图中的边当作1，表示免费使用一次，否则就当作0，这样只需判断dist[n]与k的大小，然后继续二分边长就可了。
#include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #include <queue> #include <cstdlib> #include <stack> #include <vector> #include <set> #include <map> #define LL long long #define mod 100000000 #define inf 0x3f3f3f3f #define eps 1e-9 #define N 1000010 #define FILL(a,b) (memset(a,b,sizeof(a))) #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define PII pair<int,int> using namespace std; struct edge { int to,w; edge(){} edge(int to,int w):to(to),w(w){} bool operator<(const edge &a)const{ return w>a.w; } }; vector<edge>g[N]; int n,m,k; int dis[N],vis[N]; int ok(int limit) { for(int i=1;i<=n;i++)dis[i]=inf,vis[i]=0; priority_queue<edge>que; dis[1]=0; que.push(edge(1,0)); while(!que.empty()) { edge now=que.top();que.pop(); int x=now.to; if(vis[x])continue; vis[x]=1; for(int i=0,sz=g[x].size();i<sz;i++) { int v=g[x][i].to,w=g[x][i].w>limit?1:0; if(dis[v]>dis[x]+w) { dis[v]=dis[x]+w; que.push(edge(v,dis[v])); } } } return dis[n]<=k; } int solve() { int l=0,r=N,ans=-1; while(l<=r) { int mid=(l+r)>>1; if(ok(mid))r=mid-1,ans=mid; else l=mid+1; } return ans; } int main() { while(scanf("%d%d%d",&n,&m,&k)>0) { for(int i=1;i<=n;i++)g[i].clear(); for(int i=1;i<=m;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); g[u].push_back(edge(v,w)); g[v].push_back(edge(u,w)); } printf("%d ",solve()); } }