[USACO08JAN]电话线Telephone Lines
多年以后，笨笨长大了，成为了电话线布置师。由于地震使得某市的电话线全部损坏，笨笨是负责接到震中市的负责人。该市周围分布着N(1<=N<=1000)根据1……n顺序编号的废弃的电话线杆，任意两根线杆之间没有电话线连接，一共有p(1<=p<=10000)对电话杆可以拉电话线。其他的由于地震使得无法连接。
第i对电线杆的两个端点分别是ai,bi，它们的距离为li(1<=li<=1000000)。数据中每对(ai,bi)只出现一次。编号为1的电话杆已经接入了全国的电话网络，整个市的电话线全都连到了编号N的电话线杆上。也就是说，笨笨的任务仅仅是找一条将1号和N号电线杆连起来的路径，其余的电话杆并不一定要连入电话网络。
电信公司决定支援灾区免费为此市连接k对由笨笨指定的电话线杆，对于此外的那些电话线，需要为它们付费，总费用决定于其中最长的电话线的长度(每根电话线仅连接一对电话线杆)。如果需要连接的电话线杆不超过k对，那么支出为0.
请你计算一下，将电话线引导震中市最少需要在电话线上花多少钱？
输入输出格式
输入格式：
输入文件的第一行包含三个数字n,p,k;
第二行到第p+1行，每行分别都为三个整数ai,bi,li。
输出格式：
一个整数，表示该项工程的最小支出，如果不可能完成则输出-1.
输入输出样例
输入样例：
5 7 1
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6
输出样例：
4
题意很简单，求一条路径，使这条路径的k+1大的边最小。
正解是：二分+spfa求最短路
二分出占用公司免费名额的条件，当一条边大于mid时，那条边就占用名额，统计多少条边比mid大，如果数量大于k，说明mid太小，反之mid还可以更小。
代码很简单，两个模子套一下就好了：
1 #include<algorithm> 2 #include<iostream> 3 #include<cstring> 4 #include<cstdio> 5 using namespace std; 6 int n,m,k,tot; 7 int u,v,ww,u1,v1; 8 int l,r,mid,ans=-1; 9 int q[4004000]; 10 int dis[40040]; 11 bool vis[40040]; 12 int head[40040]; 13 struct node{ 14 int to; 15 int nextt; 16 int w; 17 }a[40040]; 18 void add(int x,int y,int z) 19 { 20 a[++tot].to=y; 21 a[tot].nextt=head[x]; 22 a[tot].w=z; 23 head[x]=tot; 24 } 25 bool spfa(int x) 26 { 27 int d=0; 28 memset(vis,0,sizeof(vis)); 29 memset(dis,127/3,sizeof(dis)); 30 memset(q,0,sizeof(q)); 31 dis[1]=0; 32 vis[1]=1; 33 int headd=0,tail=1; 34 q[tail]=1; 35 while(headd<tail) 36 { 37 headd++; 38 u1=q[headd]; 39 vis[u1]=0; 40 for(int i=head[u1];i!=-1;i=a[i].nextt) 41 { 42 int flag=0; 43 v1=a[i].to; 44 if(a[i].w>mid) d=1; 45 if(dis[v1]>dis[u1]+d) 46 dis[v1]=dis[u1]+d,flag=1; 47 d=0; 48 if(vis[v1]==0&&flag) 49 { 50 tail++; 51 q[tail]=v1; 52 vis[v1]=1; 53 } 54 } 55 } 56 if(dis[n]>k) return 0; 57 else return 1; 58 } 59 int main() 60 { 61 memset(head,-1,sizeof(head)); 62 scanf("%d%d%d",&n,&m,&k); 63 for(int i=1;i<=m;i++) 64 { 65 scanf("%d%d%d",&u,&v,&ww); 66 add(u,v,ww); 67 add(v,u,ww); 68 r=max(r,ww); 69 } 70 l=0; 71 while(l<=r) 72 { 73 mid=(r+l)/2; 74 if(spfa(mid)) 75 { 76 r=mid-1;ans=mid; 77 } 78 else l=mid+1; 79 } 80 cout<<ans<<endl; 81 return 0; 82 }