题目大意

    有N个节点以及连接的P个无向边，现在要通过这P条边从1号节点连接到N号节点。若无法连接成功，则返回-1；若能够连接成功，那么其中用到了L条边，这L条边中有K条边可以免费，L-K条边不能免费，求出不能免费的边的最大长度。

题目分析

    判断能否到达，可以通过BFS搜索路径，若不能到达，返回-1；若能到达，且最少需要的路径的边数小于等于K，那么所有的边都可以免费，则返回0；若能够到达，且最少需要的路径边数大于K，则需要求出从节点1到节点N的路径中第K+1长的边的最小值，即最小化第k大的值问题。 

    用二分法，枚举边长x，若路径中大于等于x的边数大于K，则说明x在构成路径的边长序列中的序号大于K+1，则将x增大；若路径中大于等于x的边长小于等于K，则说明x在构成路径的边长序列中的序号小于等于K+1，因此将x减小.... 直到x为最小的满足路径中边长大于等于x的边数大于K的最小值，则x即为路径中第K+1大的边，且X最小。 

    那么，对于一个长度x，该选择哪条路径呢？由于要求的最小的x，那么就要求路径中边长大于等于x的个数尽可能的少（若个数少于等于K，则减小x），转换一下，将路径中长度大于等于x的边权值设为1，小于x的权值设为0，则走一条从源到汇的路径，路径中边的权值和最小即对应路径中边长大于等于x的个数最少。 

    求最短路径，使用Dijkstra算法即可。

实现(c++)

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;#define MAX_NODE 1005#define MAX_EDGE 20005#define INF 1 << 28#define min(a, b) a < b?a:b#define max(a, b) a >b? a:bstruct Edge{	int to;	int d;	int next;};struct NodeDist{	int v;	int d;	NodeDist(int vv = 0, int dd = 0) :		v(vv), d(dd){};};struct Cmp{	bool operator()(const NodeDist& e1, const NodeDist& e2){		return e1.d > e2.d;	}};Edge gEdges[MAX_EDGE];int gEdgeCount;int gHead[MAX_NODE];int gDist[MAX_NODE];bool gVisited[MAX_NODE];void InsertEdge(int u, int v, int d){	int e = gEdgeCount++;	gEdges[e].to = v;	gEdges[e].d = d;	gEdges[e].next = gHead[u];	gHead[u] = e;	e = gEdgeCount++;	gEdges[e].to = u;	gEdges[e].d = d;	gEdges[e].next = gHead[v];	gHead[v] = e;}int Dijkstra(int s, int t, int k){	memset(gVisited, false, sizeof(gVisited));	memset(gDist, 0x7F, sizeof(gDist));	gDist[s] = 0;	priority_queue
          
           , Cmp> pq; pq.push(NodeDist(s, 0)); NodeDist nd; while (!pq.empty()){ nd = pq.top(); pq.pop(); if (gVisited[nd.v]) continue; gVisited[nd.v] = true; if (nd.v == t){ break; } for (int e = gHead[nd.v]; e != -1; e = gEdges[e].next){ int v = gEdges[e].to; if (gDist[v] > gDist[nd.v] + (gEdges[e].d >= k)){ gDist[v] = gDist[nd.v] + (gEdges[e].d >= k); pq.push(NodeDist(v, gDist[v])); } } } return gDist[t];}int MinStep(int s, int t){ bool visited[MAX_NODE]; memset(visited, false, sizeof(visited)); queue
           
            
              > Q; Q.push(pair
             
              (s, 0)); visited[s] = true; while (!Q.empty()){ pair
              
                p = Q.front(); Q.pop(); if (p.first == t){ return p.second; } for (int e = gHead[p.first]; e != -1; e = gEdges[e].next){ if (!visited[gEdges[e].to]){ Q.push(pair
               
                (gEdges[e].to, p.second + 1)); visited[gEdges[e].to] = true; } } } return -1;}int gEdgeDist[MAX_EDGE];int main(){ int n, p, k, u, v, d, e_count; while (scanf("%d %d %d", &n, &p, &k) != EOF){ memset(gHead, -1, sizeof(gHead)); gEdgeCount = 0; e_count = 0; for (int i = 0; i < p; i++){ scanf("%d %d %d", &u, &v, &d); InsertEdge(u, v, d); gEdgeDist[e_count++] = d; } int min_step = MinStep(1, n); if (min_step == -1){ printf("-1\n"); continue; } else if (min_step <= k){ printf("0\n"); continue; } sort(gEdgeDist, gEdgeDist + e_count); int beg = 0, end = e_count, mid; int rr; while (beg < end){ mid = (beg + end) / 2; int t = Dijkstra(1, n, gEdgeDist[mid]); if (t <= k){ end = mid; } else{ rr = gEdgeDist[mid]; beg = mid + 1; } } //最后得到的是，满足路径中边长大于等于 x 的长度的边数 大于k 最大的 x printf("%d\n", rr); } return 0;}