题目大意
有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<stdio.h>
#include<string.h>
#include<vector>
#include<queue>
#include<algorithm>
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:b
struct 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<NodeDist, vector<NodeDist>, 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<pair<int, int> > Q;
Q.push(pair<int, int>(s, 0));
visited[s] = true;
while (!Q.empty()){
pair<int, int> 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<int, int>(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
");
continue;
}
else if (min_step <= k){
printf("0
");
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
", rr);
}
return 0;
}