[C++] PAT 1018 Public Bike Management (30分)

Sample Input:

10 3 3 5 6 7 0 0 1 1 0 2 1 0 3 3 1 3 1 2 3 1

Sample Output:

3 0->2->3 0

题解：

此题直接使用Djkstra+DFS，但要注意的是在经历每个点的时候就进行调整，而不是遍历完整个最短路径后进行调整，例： take表示从s₀带出的自行车数量，re表示带回的自行车数量 1.从s₀到s₁时，take=2，re=0 2.从s₁到s₂时，take=2，re=3 3.从s₂到s₃时，take=2，re=7 4.从s₃到s₄时，发现s₄需要5辆自行车，take=2，re=2 5.从s₄返回 那么最后的结果是take=2和re=2，而不是遍历整个路径后再进行调整的结果take=re=0

#include <iostream> #include <queue> #include <map> #include <vector> #include <stack> using namespace std; const int MAXV = 510; struct cmp{ bool operator()(pair<int,int>&a,pair<int,int>&b){ return a.second > b.second; } }; int n,c,t,m,G[MAXV][MAXV]; int capacity[MAXV]; int d[MAXV]; vector<int> pre[MAXV]; int take=100000,re=100000; vector<int> temp_short_path; vector<int> opt_short_path; priority_queue<pair<int,int>,vector<pair<int,int>>,cmp> q; void solve(){ fill(d,d+MAXV,10000000); q.push(make_pair(0,0)); d[0] = 0; while(!q.empty()){ pair<int,int> temp = q.top(); int first = temp.first; q.pop(); for(int i=0;i<=n;i++){ if(G[first][i] != -1){ int dis = d[first] + G[first][i]; if(dis < d[i]){ d[i] = dis; pre[i].clear(); pre[i].push_back(first); q.push(make_pair(i,d[i])); } else if(dis == d[i]){ pre[i].push_back(first); } } } } } void dfs(int t){ temp_short_path.push_back(t); if(t == 0) { int need = 0, back = 0; for(int i = temp_short_path.size() - 1; i >= 0; i--) { int id = temp_short_path[i]; if(capacity[id] > 0) { back += capacity[id]; } else { if(back > (0 - capacity[id])) { back += capacity[id]; } else { need += ((0 - capacity[id]) - back); back = 0; } } } if(need < take) { take = need; re = back; opt_short_path = temp_short_path; } else if(need == take && back < re) { re = back; opt_short_path = temp_short_path; } temp_short_path.pop_back(); return ; } for(int i = 0; i < pre[t].size(); i++) dfs(pre[t][i]); temp_short_path.pop_back(); } int main(){ cin >> c >> n >> t >> m; for(int i=1;i<=n;i++){ scanf_s("%d",&capacity[i]); capacity[i] = capacity[i] - c / 2; } fill(G[0],G[0]+MAXV*MAXV,-1); int temp_f,temp_t,temp_w; for(int i=0;i<m;i++){ cin >> temp_f >> temp_t >> temp_w; G[temp_f][temp_t] = temp_w; G[temp_t][temp_f] = temp_w; } solve(); dfs(t); cout << take << " "; for(int i=opt_short_path.size()-1;i>=0;i--){ if(i != 0 ){ cout << opt_short_path[i] << "->"; } else{ cout << opt_short_path[i]; } } cout << " " << re; system("pause"); return 0; }