PAT1018 Public Bike Management【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\n", ans_take);
129     
130     return 0;    
131 }