题目大意：给出一个图，顶点为1到n和一个值k，求出包含顶点1到顶点n的通路的子图中，第k+1大的边最短为多少？（若存在一条从1到n路径边数小于等于k，则返回0，若不存在通路，返回-1）

  思路：一开始我连题都看错了，还以为是动规，汗···

  很显然，此题不好从正面下手，即如果从找到路径下手的话会变得相当棘手，于是想到枚举边，以某一边作为子图中第k+1大的边，看是否是可行解：比它大的边的权值为1，反之为0，用spfa算出1到n的最短路，若路径长大于k则二分查找比m更大的边，反之则查找更小的边，并可用e[0]=0表示权值为零的边（即路径上边数小于k），这样就不难得出正确解了。算法时间为O(nlgn)。

代码如下：

#include 
     
      #include 
      
       using namespace std;ifstream fin("phone.in");ofstream fout("phone.out");int graph[1001][1001],matrix[1001][1001];bool status[10001];typedef struct{int start,end;int w;}Bian;Bian bian[10001];int d[1001];int Q[10001];int partion(Bian *a,int start,int end){int j=start-1;Bian t;for(int i=start;i<=end;i++){if(a[i].w<=a[end].w){j++;t=a[i];a[i]=a[j];a[j]=t;}}return j;}int quicksort(Bian *a,int start,int end){if(start>=end)return 0;int j=partion(a,start,end);quicksort(a,start,j-1);quicksort(a,j+1,end);return 0;}int initial(int n){for(int i=0;i<=n;i++)d[i]=10000000;return 0;}int spfa(Bian *m,int n){initial(n);d[1]=0;int head=1,tail=1,t=0,i=0,x=0;Q[1]=1;while(((tail+1)000)!=head){t=Q[head];head++;head%=10000;for(i=1;i<=graph[t][0];i++){x=0;if(matrix[t][graph[t][i]]>m->w)x=1;if(d[graph[t][i]]>d[t]+x){d[graph[t][i]]=d[t]+x;tail++;Q[tail]=graph[t][i];tail%=10000;}}}return d[n];}int bins(int n,int p,int start,int end,int k){if((end<0||start>p)||(start>end))return -1;int m=(start+end)/2;if(spfa(&bian[m],n)>k)return bins(n,p,m+1,end,k);else{int t=bins(n,p,start,m-1,k);if(t==-1)return m;return t;}}int main(){ios::sync_with_stdio(0);int N=0,P=0,K=0,i=0,x=0,y=0,z=0;fin>>N>>P>>K;for(i=1;i<=P;i++){fin>>x>>y>>z;graph[x][0]++;graph[x][graph[x][0]]=y;graph[y][0]++;graph[y][graph[y][0]]=x;matrix[x][y]=z;matrix[y][x]=z;bian[i].start=x;bian[i].end=y;bian[i].w=z;}quicksort(bian,1,P);i=bins(N,P,0,P,K);if(i<0)fout<<-1<
       
        <
        
         <
        
       
      
     

  这道题说明将适当的对象作为枚举对象是重要的思想方法。