当前位置：网站首页>PAT. A1018 Public Bike Management

PAT. A1018 Public Bike Management

2022-07-18 00:48:00 【51CTO】

PAT.A1018 Public Bike Management_#include

PAT.A1018 Public Bike Management_ Shortest path _02

The question

There are some public bicycle stations in the city , The maximum capacity of bicycles at each station is an even number Cmax, And if the number of bicycles in a station happens to be Cmax/2, Then the station is called “ Perfect state ”. If the capacity of a station is full or empty , Then the control center (PBMC) Will carry or collect a certain number of bicycles from the road to the station , So that the problem station and all stations along the way can reach “ Perfect state ”. Now give Cmax、 Number of stations N ( Excluding Control Center PBMC)、 Question station number Sp、 Undirected edge number M And edge right , Ask for a way from PBMC ( Write it down as 0 Number ) Arrive at the problem station Sp Shortest path , The output needs to be from PBMC Number of bicycles carried 、 Shortest path 、 The number of bicycles to be brought back after arriving at the station in question . If there are multiple shortest paths , Then choose from PBMC The one who carries the least number of bicycles : If there are still multiple , Then choose the one with the least number of bicycles brought back from the station in question . Be careful : The adjustment process of all stations along the way must be completed in the process of going to the problem station , No adjustment when bringing back .

Examples （ Replicable ）

Be careful

The idea of solving this problem is Djikstra+DFS. Specific for ： First use Dijkstra Find the shortest path , In the process of finding , Record the precursor node of each node of each path . Use DFS Start from the problem site , Use the precursor node just recorded to return to PBMC, Write down the path , Again from PBMC Calculate the number of bicycles you need to take when you leave need And the number of bicycles that need to be retrieved remain, And minneed and minremain Compare , Update shortest path .

       
       #include<bits/stdc++.h>
       
       using 
       
       namespace 
       
       std;
       
       int 
       
       Cmax,
       
       n,
       
       sp,
       
       m,
       
       minneed
       
       =
       
       INT_MAX,
       
       minremain
       
       =
       
       INT_MAX;
       
       //Cmax Is the maximum capacity ,n For the top points ,sp For the problem site ,m Number of sides 
       
       int 
       
       G[
       
       510][
       
       510],
       
       weight[
       
       510],
       
       dis[
       
       510];
       
       //G Figure ,weight Is the number of single cars in the station ,dis Is the distance to a node 
       
       bool 
       
       vis[
       
       510]
       
       ={
       
       false};
       
       // Mark whether the node has been accessed 
       
       vector
       
       <
       
       int
       
       > 
       
       temp,
       
       path,
       
       pre[
       
       510];
       
       //temp Is a temporary path ,path Is the shortest path ,pre Storage precursor node 
       
       void 
       
       Dijkstra(){
       
       fill(
       
       dis,
       
       dis
       
       +
       
       n
       
       +
       
       1,
       
       INT_MAX); 
       
       // Notice that the second parameter is dis+n+1
       
       dis[
       
       0]
       
       =
       
       0;
       
       while(
       
       !
       
       vis[
       
       sp]){
       
       int 
       
       v,
       
       minn
       
       =
       
       INT_MAX;
       
       for(
       
       int 
       
       i
       
       =
       
       0;
       
       i
       
       <=
       
       n;
       
       i
       
       ++){
       
       if(
       
       !
       
       vis[
       
       i]
       
       &&
       
       dis[
       
       i]
       
       <
       
       minn){
       
       minn
       
       =
       
       dis[
       
       i];
       
       v
       
       =
       
       i;
       
            }
       
        }    
       
       vis[
       
       v]
       
       =
       
       true;
       
       for(
       
       int 
       
       i
       
       =
       
       0;
       
       i
       
       <=
       
       n;
       
       i
       
       ++){
       
       if(
       
       !
       
       vis[
       
       i]
       
       &&
       
       G[
       
       v][
       
       i]
       
       !=
       
       0
       
       &&
       
       dis[
       
       i]
       
       >
       
       dis[
       
       v]
       
       +
       
       G[
       
       v][
       
       i]){
       
       dis[
       
       i]
       
       =
       
       dis[
       
       v]
       
       +
       
       G[
       
       v][
       
       i];
       
       pre[
       
       i].
       
       clear();
       
       pre[
       
       i].
       
       push_back(
       
       v);
       
            }
       
       else 
       
       if(
       
       !
       
       vis[
       
       i]
       
       &&
       
       G[
       
       v][
       
       i]
       
       !=
       
       0
       
       &&
       
       dis[
       
       i]
       
       ==
       
       dis[
       
       v]
       
       +
       
       G[
       
       v][
       
       i]){
       
       pre[
       
       i].
       
       push_back(
       
       v);
       
            }
       
        }
       
    }
       
}
       
       void 
       
       DFS(
       
       int 
       
       v){
       
       temp.
       
       push_back(
       
       v);
       
       if(
       
       v
       
       ==
       
       0){
       
       int 
       
       need
       
       =
       
       0,
       
       remain
       
       =
       
       0;
       
       for(
       
       int 
       
       i
       
       =
       
       temp.
       
       size()
       
       -
       
       1;
       
       i
       
       >=
       
       0;
       
       i
       
       --){
       
       // Note that from the back to the front is from PBMC The path to the problem site 
       
       int 
       
       now
       
       =
       
       temp[
       
       i];
       
       if(
       
       weight[
       
       now]
       
       >=
       
       0){
       
       remain
       
       +=
       
       weight[
       
       now];
       
            }
       
       else{
       
       if(
       
       remain
       
       >
       
       abs(
       
       weight[
       
       now])){
       
       remain
       
       +=
       
       weight[
       
       now];
       
                }
       
       else{
       
       need
       
       +=
       
       abs(
       
       weight[
       
       now])
       
       -
       
       remain;
       
       remain
       
       =
       
       0;
       
                }
       
            }
       
        }
       
       if(
       
       need
       
       <
       
       minneed){
       
       path
       
       =
       
       temp;
       
       minneed
       
       =
       
       need;
       
       minremain
       
       =
       
       remain;
       
        }
       
       else 
       
       if(
       
       need
       
       ==
       
       minneed
       
       &&
       
       remain
       
       <
       
       minremain){
       
       path
       
       =
       
       temp;
       
       minneed
       
       =
       
       need;
       
       minremain
       
       =
       
       remain;
       
        }
       
       temp.
       
       pop_back();
       
       return;
       
    }
       
       for(
       
       int 
       
       i
       
       =
       
       0;
       
       i
       
       <
       
       pre[
       
       v].
       
       size();
       
       i
       
       ++)
       
       DFS(
       
       pre[
       
       v][
       
       i]);
       
       temp.
       
       pop_back();
       
}
       
       int 
       
       main(){
       
       cin
       
       >>
       
       Cmax
       
       >>
       
       n
       
       >>
       
       sp
       
       >>
       
       m;
       
       for(
       
       int 
       
       i
       
       =
       
       1;
       
       i
       
       <=
       
       n;
       
       i
       
       ++){
       
       scanf(
       
       "%d",
       
       &
       
       weight[
       
       i]);
       
       weight[
       
       i]
       
       -=
       
       Cmax
       
       /
       
       2; 
       
    } 
       
       int 
       
       u,
       
       v,
       
       w;
       
       while(
       
       m
       
       --){
       
       scanf(
       
       "%d%d%d",
       
       &
       
       u,
       
       &
       
       v,
       
       &
       
       w);
       
       G[
       
       u][
       
       v]
       
       =
       
       G[
       
       v][
       
       u]
       
       =
       
       w;
       
    }
       
       Dijkstra();
       
       DFS(
       
       sp);
       
       printf(
       
       "%d ",
       
       minneed);
       
       for(
       
       int 
       
       i
       
       =
       
       path.
       
       size()
       
       -
       
       1;
       
       i
       
       >=
       
       0;
       
       i
       
       --){
       
       printf(
       
       "%d",
       
       path[
       
       i]);
       
       if(
       
       i
       
       >
       
       0)
       
       printf(
       
       "->");
       
    }
       
       printf(
       
       " %d",
       
       minremain);
       
       return 
       
       0;
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.