多年以后，笨笨长大了，成为了电话线布置师。由于地震使得某市的电话线全部损坏，笨笨是负责接到震中市的负责人。该市周围分布着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.
请你计算一下，将电话线引导震中市最少需要在电话线上花多少钱？ ——by洛谷（洛谷少有的良心翻译）
https://www.luogu.org/problem/show?pid=1948
二分答案＋有条件的最短路；
- 二分可能的答案，即对读入的边长sort，然后二分
- 对于每个答案跑SPFA（因为手头有SPFA板子）
- SPFA的松弛为spf[x[i].to]=spf[que[h]]+(x[i].dis>ct?1:0)（ct为二分的答案，意味着如果本边长度大于答案，则让这条边占用公司的名额）
- 若spf[n]>k，则把n连入时不可能以当前答案为答案（因为以当前答案为答案，占用名额一定大于k）
代码如下：
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 struct ss 6 { 7 int to,next,dis; 8 }x[20001]; 9 int first[1001]; 10 int d[10001]; 11 int que[10000],vis[1001],spf[1001]; 12 int n,pd,k,num,p; 13 void build(int f,int t,int di) 14 { 15 x[++num].next=first[f]; 16 x[num].to=t; 17 x[num].dis=di; 18 first[f]=num; 19 } 20 void spfa(int ,int ); 21 int main() 22 { 23 int i,j,l,r,mid; 24 scanf("%d%d%d",&n,&p,&k); 25 for(i=1;i<=p;i++) 26 { 27 scanf("%d%d%d",&j,&l,&d[i]); 28 build(j,l,d[i]); 29 build(l,j,d[i]); 30 } 31 sort(d+1,d+p+1); 32 l=0;r=p;mid=(l+r)/2; 33 while(l<r) 34 { 35 memset(spf,(0x3f3f3f),sizeof(spf)); 36 pd=0; 37 spfa(1,d[mid]); 38 if(pd==1) 39 { 40 r=mid; 41 mid=(l+r)/2; 42 } 43 else 44 { 45 l=mid+1; 46 mid=(l+r)/2; 47 } 48 } 49 if(r==p&&pd==0)d[r]=-1; 50 printf("%d",d[r]); 51 return 0; 52 } 53 void spfa(int s,int ct) 54 { 55 int h=0,t=1,i; 56 spf[s]=0; 57 que[t]=s;vis[s]=1; 58 while(h<t) 59 { 60 h++; 61 vis[que[h]]=0; 62 i=first[que[h]]; 63 while(i!=0) 64 { 65 if(spf[x[i].to]>spf[que[h]]+(x[i].dis>ct?1:0)) 66 { 67 spf[x[i].to]=spf[que[h]]+(x[i].dis>ct?1:0); 68 if(vis[x[i].to]==0) 69 { 70 t++; 71 que[t]=x[i].to; 72 vis[que[t]]=1; 73 } 74 } 75 i=x[i].next; 76 } 77 } 78 if(spf[n]<=k) 79 pd=1; 80 return ; 81 }
祝AC哟；