二分+最短路

Time Limit:1000MS     Memory Limit:65536KB     64bit IO Format:%lld & %llu

Description

多年以后，笨笨长大了，成为了电话线布置师。由于地震使得某市的电话线全部损坏，笨笨是负责接到震中市的负责人。该市周围分布着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.

请你计算一下，将电话线引导震中市最少需要在电话线上花多少钱？

Input

输入文件的第一行包含三个数字n,p,k;

第二行到第p+1行，每行分别都为三个整数ai,bi,li。

Output

一个整数，表示该项工程的最小支出，如果不可能完成则输出-1.

Sample Input

5 7 11 2 53 1 42 4 83 2 35 2 93 4 74 5 6

Sample Output

4

 

 

//挺有意思的一道题，要使第 k+1 大的边的值越小越好。想不到啊，spfa还能这么用，二分还能这么用。。。

我觉得最神奇的一点是，最后的一次满足情况的 mid (即 ans )一定是第是这个图里面的边，并且这个值是第 k+1 大的边最小的情况。

因为，小于这个值的话，这条边也会让 dis[n] 的值加 1 ，即不会满足 dis[n]<=k 的

79ms

1 #include 
          
            2 #include 
           
             3  4 #define MAXN 1005 5  6 struct Edge{ 7     int v,w; 8     int next; 9 }edge[30005];10 int headlist[MAXN];11 12 int n,p,k,bian=0;13 14 void join(int a,int b,int c)15 {16     bian++;17     edge[bian].v=b;18     edge[bian].w=c;19     edge[bian].next=headlist[a];20     headlist[a]=bian;21 }22 23 int Q[1000];24 int vis[MAXN];25 int dis[MAXN];//大于limit的最少有多少个26 int spfa(int limit)27 {28     for (int i=1;i<=n;i++)29         dis[i]=10000000;//kanknkkkkkkkkkkkkk30     memset(vis,0,sizeof(vis));31 32     Q[0]=1;33     int l=0,r=1;34     dis[1]=0,vis[1]=1;35     while (l!=r)36     {37         int now=Q[l++];38         if (l==1000) l=0;39         vis[now]=0;40         int i=headlist[now];41         int mm=dis[now];42         while (i)43         {44             if (edge[i].w>limit) mm=dis[now]+1;45             else mm=dis[now];46             if (mm