PAT1018 Public Bike Management【dfs】【最短路】

题目：https://pintia.cn/problem-sets/994805342720868352/problems/994805489282433024

题意：

给定一个图，一个目的地和每个节点上的自行车数量。

现在要找到从0到目的地的一条最短路，并且对这条路径上的点的自行车数目进行调度使得每个节点的自行车数量都是某个定值。

可以从前面经过的节点搬运自行车到后面的节点，0号节点的自行车是无穷多的。

如果最短路不唯一，要求找到从0号带出的自行车数量最小的方案。

如果还是不唯一，要求找到带回0号的自行车数量最小的方案。

思路：

刚开始直接就想要同时最优化路径和调度车数量跑dijkstra了。但是这样是不对的。

应该要先完最短路，否则会出现前面的某个节点就出现了最短路相同而选择了另一条车少的但是影响了后面的最短路。

总之就是这样跑出来的最短路，并不是时间最短的。

所以我们应该要先跑最短路，然后再在几条最短路里面搜索他们各自调度自行车的数量。这里用dfs

每次搜索到了目的地就看看是不是比原答案更优。

  1 //#include<bits/stdc++>
  2 #include<stdio.h>
  3 #include<iostream>
  4 #include<algorithm>
  5 #include<cstring>
  6 #include<stdlib.h>
  7 #include<queue> 
  8 #include<map>
  9 #include<stack>
 10 #include<set>
 11 
 12 #define LL long long
 13 #define ull unsigned long long
 14 #define inf 0x7f7f7f7f 
 15 
 16 using namespace std;
 17 
 18 int cmax, n, spro, m, perf;
 19 const int maxn = 505;
 20 vector<pair<int, int> > g[maxn];
 21 int bike_num[maxn];
 22 
 23 bool vis[maxn];
 24 int d[maxn];
 25 int cnt[maxn];
 26 int prv[maxn];
 27 
 28 int findmin()
 29 {
 30     int mmm = inf, id = -1;
 31     for(int i = 0; i <= n; i++){
 32         if(!vis[i] && d[i] < mmm){
 33             mmm = d[i];
 34             id = i;
 35         }
 36     }
 37     return id;
 38 }
 39 void dijkstra()
 40 {
 41     memset(d, 0x3f, sizeof(d));
 42     for(int i = 0; i < g[0].size(); i++){
 43         d[g[0][i].first] = g[0][i].second;
 44     }
 45     vis[0] = true;
 46     d[0] = 0;
 47     
 48     while(1){
 49 //        int mmm = inf, id;
 50 //        for(int j = 0; j <= n; j++){
 51 //            if(d[j] < mmm && !vis[j]){
 52 //                mmm = d[j];
 53 //                id = j;
 54 //            }
 55 //        }
 56         int id = findmin();
 57         if(id == -1)break;
 58         vis[id] = true;
 59         for(int j = 0; j < g[id].size(); j++){
 60             int v = g[id][j].first, t = g[id][j].second;
 61             if(d[id] + t < d[v]){
 62                 d[v] = d[id] + t;
 63             }
 64         }
 65         
 66     }
 67 }
 68 
 69 int bring, take;
 70 int ans_bring = inf, ans_take = inf;
 71 vector<int>path, ans_path;
 72 void dfs(int u)
 73 {
 74     if(u == spro){
 75         if(ans_bring > bring || ans_bring == bring && ans_take > take){
 76             ans_bring = bring;
 77             ans_take = take;
 78             ans_path = path;
 79             return;
 80         }
 81     }
 82     for(int i = 0; i < g[u].size(); i++){
 83         int v = g[u][i].first, t = g[u][i].second;
 84         int tmpbring = bring, tmptake = take;
 85         
 86         if(!vis[v] && t + d[u] == d[v]){
 87             vis[v] = true;
 88             path.push_back(v);
 89             take += bike_num[v];
 90             if(take < 0){
 91                 bring -= take;
 92                 take = 0;
 93             }
 94             dfs(v);
 95             vis[v] = false;
 96             path.pop_back();
 97             bring = tmpbring;
 98             take = tmptake;
 99         }
100     }
101 }
102 
103 int main()
104 {
105     scanf("%d%d%d%d", &cmax, &n, &spro, &m);
106     perf = cmax / 2;
107     for(int i = 1; i <= n; i++){
108         scanf("%d", &bike_num[i]);
109         bike_num[i] -= perf;
110     }
111     for(int i = 0; i < m; i++){
112         int u, v, t;
113         scanf("%d%d%d", &u, &v, &t);
114         g[u].push_back(make_pair(v, t));
115         g[v].push_back(make_pair(u, t));
116     }
117     
118     dijkstra();
119     //cout<<d[spro]<<endl;
120     memset(vis, 0, sizeof(vis));
121     vis[0] = true;
122     dfs(0);
123     
124     printf("%d 0", ans_bring);
125     for(int i = 0; i < ans_path.size(); i++){
126         printf("->%d", ans_path[i]);
127     } 
128     printf(" %d
", ans_take);
129     
130     return 0;    
131 }