题目链接：
题目大意：
求一条路径从1到n使第k+1大的边最小。
解题思路：
二分答案mid，当原边权小于等于mid新边权为0，否则新边权为1.
求最短路，若小于等于k说明满足条件
注意：最开始的l必须是0，而不是这些边中的最小边，因为最小化第k+1大的话答案可能为0
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #define MID(l, r) (l + (r - l) / 2) 8 #define lson(o) (o * 2) 9 #define rson(o) (o * 2 + 1) 10 using namespace std; 11 typedef long long ll; 12 const int INF = 1e9 +7; 13 const int maxn = 1e6 + 10; 14 int n, m, k; 15 struct edge{ 16 int u, v, w; 17 edge(int u, int v, int w):u(u), v(v), w(w){} 18 edge(){} 19 }; 20 struct Heapnode 21 { 22 int d, u; 23 Heapnode(){} 24 Heapnode(int d, int u):d(d), u(u){} 25 bool operator <(const Heapnode & a)const 26 { 27 return d > a.d; 28 } 29 }; 30 bool v[maxn]; 31 int d[maxn]; 32 33 int dijkstra(int s, int t, vector edges, vector G[]) 34 { 35 priority_queue q; 36 for(int i = 0; i <= n; i++)d[i] = INF; 37 d[s] = 0; 38 memset(v, 0, sizeof(v)); 39 q.push(Heapnode(0, s)); 40 while(!q.empty()) 41 { 42 Heapnode now = q.top(); 43 q.pop(); 44 int u = now.u; 45 if(v[u])continue; 46 v[u] = 1; 47 for(int i = 0; i < G[u].size(); i++) 48 { 49 edge& e = edges[G[u][i]]; 50 int v = e.v; 51 if(d[v] > d[u] + e.w) 52 { 53 d[v] = d[u] + e.w; 54 q.push(Heapnode(d[v], v)); 55 } 56 } 57 } 58 return d[t]; 59 } 60 61 vector edges; 62 vector G[maxn]; 63 vector edges2; 64 void addedge(int u, int v, int w) 65 { 66 edges.push_back(edge(u, v, w)); 67 int m = edges.size(); 68 G[u].push_back(m - 1); 69 } 70 void init(int mid) 71 { 72 edges2.clear(); 73 for(int i = 0; i < edges.size(); i++) 74 { 75 edge& e = edges[i]; 76 if(e.w <= mid) 77 { 78 edges2.push_back(edge(e.u, e.v, 0)); 79 } 80 else 81 { 82 edges2.push_back(edge(e.u, e.v, 1)); 83 } 84 } 85 } 86 int main() 87 { 88 scanf("%d%d%d", &n, &m, &k); 89 int l = 0, r = 0, u, v, w; 90 while(m--) 91 { 92 scanf("%d%d%d", &u, &v, &w); 93 addedge(u, v, w); 94 addedge(v, u, w); 95 r = max(r, w); 96 } 97 int ans = -1; 98 while(l <= r)//l最开始要设置成0，不能设置成最小边，因为第k大可能为0 99 {100 int mid = (l + r) / 2;101 init(mid);102 int t = dijkstra(1, n, edges2, G);103 //cout< <<" "< <
