Links: Lougu Valley
Title Description
Farmer John wants to set up a telephone line at his farm. Unfortunately, the phone company is uncooperative, so he needs to pay for some of the cables required to connect his farm to the phone system.
There are N (1 ≤ N ≤ 1,000) forlorn telephone poles conveniently numbered 1..N that are scattered around Farmer John's property; no cables connect any them. A total of P (1 ≤ P ≤ 10,000) pairs of poles can be connected by a cable; the rest are too far apart.
The i-th cable can connect the two distinct poles Ai and Bi, with length Li (1 ≤ Li ≤ 1,000,000) units if used. The input data set never names any {Ai, Bi} pair more than once. Pole 1 is already connected to the phone system, and pole N is at the farm. Poles 1 and N need to be connected by a path of cables; the rest of the poles might be used or might not be used.
As it turns out, the phone company is willing to provide Farmer John with K (0 ≤ K < N) lengths of cable for free. Beyond that he will have to pay a price equal to the length of the longest remaining cable he requires (each pair of poles is connected with a separate cable), or 0 if he does not need any additional cables.
Determine the minimum amount that Farmer John must pay.
Many years later, he grew up and became a telephone line arranger.Since the earthquake destroyed all the telephone lines in a city, Dumb is the person in charge of receiving the earthquake.The city is surrounded by n (1<=n<=1000) according to 1...n Sequentially numbered abandoned telephone poles, no telephone line connection between any two poles, a total of P (1<=p<=10000) can pull the telephone line to the pole.Others are not connected due to earthquakes.
The first two ends of the pole are AI and bi, and their distances are Li (1<=li<=1000000).Each pair (ai,bi) occurs only once in the data.The pole number 1 is connected to the national telephone network, and the city's telephone lines are all connected to the pole number N.That is, the clumsy task is simply to find a path connecting poles 1 and N. The rest of the poles don't have to be connected to the telephone network.
The telecommunications company decided to support the disaster area in connecting k pairs of telephone poles designated by the clumsy and clumsy people for free. For those other telephone lines, the total cost depends on the length of the longest one (only one pair of telephone poles per telephone line).If the poles to be connected do not exceed k pairs, the cost is 0.
Please calculate how much it will cost to guide the epicenter through the telephone line at least?
Input Format
The first line of the input file contains three numbers n,p,k;
Lines 2 through p+1, each with three integers ai,bi,li.
Output Format
An integer that represents the minimum cost of the project and outputs -1 if it is not possible to complete.
Input and Output Samples
input
5 7 1 1 2 5 3 1 4 2 4 8 3 2 3 5 2 9 3 4 7 4 5 6
output
4
Explain
There are 5 poles. Pole 1 cannot be connected directly to poles 4 or 5. Pole 5 cannot be connected directly to poles 1 or 3. All other pairs can be connected. The phone company will provide one free cable.
If pole 1 is connected to pole 3, pole 3 to pole 2, and pole 2 to pole 5 then Farmer John requires cables of length 4, 3, and 9. The phone company will provide the cable of length 9, so the longest cable needed has length 4.
Topic:
Given an undirected power map, the weight represents the cost of building a power line, and the company reimburses K lines, the person who needs to pay the most for the remaining lines.
Find a path from Node 1 to Node N on the weighted undirected graph to minimize the edge weight of the largest K+1 on the path
Reflection:
Why can I generalize this way?Because the answer in the question is the smallest, we are greedy and sure to run out of K free qualifications, then the most cost-effective plan is to take the longest K roads for free and then pay for the length of the k+1 roads.Such greedy ideas are clearly correct.
Problem: (First paste a better link to the problem https://www.luogu.org/problemnew/solution/P1948)
Shortest path problem, but at this time the shortest path is not the shortest distance, but given a cost X, whether there is a path to satisfy, exactly K+1 path to satisfy >=X, this X is the feasible solution.Divide to find the smallest possible solution!
So at this point, it is no longer meaningful to shorten the distance of the d[] array, but the minimum number of edges to reach the end >=X.
Specific points are as follows:
We can divide the maximum cost of mid into [l,r],(l is the minimum cost, R is the maximum cost), then treat edges greater than or equal to mid as edges with a weight of 1, edges less than mid as edges with a weight of zero, and then find the shortest path from point 1 to point n. If the length of the shortest path is greater than k, the logarithm of the connection is greater than k pairs.Continue the duplicate search in [mid,r]; if the shortest path length is less than k, the logarithm of the connection is smaller than k. Continue the duplicate search in [l,mid], and finally, L is the requirement.
1 #include <stdio.h> 2 #include <string.h> 3 #include <iostream> 4 #include <string> 5 #include <math.h> 6 #include <algorithm> 7 #include <queue> 8 const int INF=0x3f3f3f3f; 9 using namespace std; 10 const int maxlen=1000000; 11 int D[1005];//"Minimum distance ", record greater than or equal to mid How many edges are there! 12 13 struct Edge{ 14 int to; 15 int cost; 16 }; 17 vector<Edge> G[1005];//edge 18 // pair<int,int> For shortest path, vertex number 19 int n,p,k; 20 21 //Dijkstra Algorithm.When a point that does not belong to a collection is included, instead of updating the shortest path, it is necessary to update to reach this point.>=mid How many edges! 22 bool judge(int mid) 23 { 24 priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >qe; 25 fill(D,D+n+2,INF);//Initialize the array, remember that the length is n+2 26 D[1]=0;//Starting point 27 qe.push(make_pair(0,1)); 28 while(qe.size()) 29 { 30 pair<int,int> P=qe.top(); 31 qe.pop(); 32 int u=P.second; 33 if(D[u]<P.first) 34 continue; 35 for(int i=0;i<G[u].size();i++) 36 { 37 Edge e=G[u][i]; 38 int dd;//Record greater than or equal to mid Of. 39 if(e.cost>=mid) 40 dd=D[u]+1; 41 else 42 dd=D[u]; 43 if(D[e.to]>dd) 44 { 45 D[e.to]=dd; 46 qe.push(make_pair(D[e.to],e.to)); 47 } 48 } 49 } 50 return D[n]>=k+1; 51 //k+1 This boundary is the last possible solution! 52 // because>=mid Yes K+1 Notes mid There happens to be on the right K Free, at this time mid Is the best solution. 53 //So those that meet this condition mid That is the answer. 54 } 55 56 int main() 57 { 58 scanf("%d %d %d",&n,&p,&k); 59 for(int i=1;i<=p;i++) 60 { 61 int a,b,c; 62 scanf("%d %d %d",&a,&b,&c); 63 G[a].push_back(Edge{b,c}); 64 G[b].push_back(Edge{a,c}); 65 } 66 int l=0,r=maxlen+2;//Be careful r=maxlen+2，Otherwise, it will not output-1 67 while(r-l>1) 68 { 69 int mid=(r+l)/2; 70 if(judge(mid)) 71 l=mid; 72 else 73 r=mid; 74 } 75 if(l>maxlen) 76 printf("-1\n"); 77 else 78 printf("%d\n",l); 79 return 0; 80 }
There is also a dp method (from the link to the above question)
Consider using f[i][j]f[i][j] to represent 1-point i, using the minimum cost of J free lines.
This state space is 1000*1000 and can be saved.
For an edge e, u->v, we have the following transfer
Free line not required: f[v][k] = min(f[v][k],max(f[u][k],len[e])
Use free line: f[v][k+1]=min(f[v][k+1],f[u][k])
Not a DAG graph is considered, and there is no definite order to dp, so we use spfa to transfer these states.Think of each state as a point, connect the edges according to the above transition, and then run the shortest path to find the minimum value of each state.Of course, we don't really need to build such a 1e6-point map when we are actually doing it. We just need to sort when we are relaxed, see the code in detail.
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<queue> 6 #include<vector> 7 #include<cstring> 8 #include<cmath> 9 #include<set> 10 using namespace std; 11 12 const int maxn = 1005, maxm = 20005; 13 int n,p,k; 14 int h[maxn],nxt[maxm],to[maxm],len[maxm],tot; 15 int dis[maxn][maxn]; 16 bool vis[maxn][maxn]; 17 struct Node{ 18 int u,k;//Save the current point and used free lines 19 Node(int x,int y){ 20 u = x; k = y; 21 } 22 void operator=(const Node b){ 23 u = b.u; k = b.k; 24 } 25 void is(int x,int y){ 26 u = x; k = y; 27 } 28 }; 29 30 inline void spfa(){ 31 memset(dis,0x2f,sizeof(dis)); 32 queue<Node> q; 33 Node a(1,0);//Boundary conditions, f[1][0] = 0 34 q.push(a); vis[1][0] = 1; dis[1][0] = 0; 35 while(!q.empty()){ 36 a = q.front(); q.pop(); 37 int u =a.u, uk = a.k; //Remove the current point and the number of free lines currently in use 38 vis[u][uk] = 0; 39 for(int i=h[u],v;i;i=nxt[i]){ 40 v = to[i]; 41 //No Free Line 42 if(max(dis[u][uk],len[i]) < dis[v][uk]){ 43 dis[v][uk] = max(dis[u][uk],len[i]); 44 if(!vis[v][uk]){ 45 a.is(v,uk); 46 q.push(a); vis[v][uk] = 1; 47 } 48 } 49 //Use the free line 50 if(uk < k && dis[u][uk] < dis[v][uk+1]){ 51 dis[v][uk+1] = dis[u][uk]; 52 if(!vis[v][uk+1]){ 53 a.is(v,uk+1); 54 q.push(a); vis[v][uk+1] = 1; 55 } 56 } 57 } 58 } 59 } 60 61 int main(){ 62 cin>>n>>p>>k; 63 for(int i=1;i<=p;i++){ 64 int u,v,w; cin>>u>>v>>w; 65 to[++tot] = v; nxt[tot] = h[u]; len[tot] = w; h[u] = tot; 66 to[++tot] = u; nxt[tot] = h[v]; len[tot] = w; h[v] = tot; 67 } 68 spfa(); 69 //Judging that unsolvable 791621423 is initially assigned INF 70 if(dis[n][k] == 791621423) cout<<-1<<endl; 71 else cout<<dis[n][k]<<endl; 72 return 0; 73 }