1018 Public Bike Management
比较复杂的模拟题，Dijstra和dfs结合，注意记牢回溯算法框架：
#include<bits/stdc++.h>
using namespace std;
#define ipair pair<int,int>
int cmax,n,sp,m;
vector<vector<int>> pre;
vector<vector<ipair>> graph;
vector<int> num,dis,temp,res;
int minNeed=INT_MAX,minBack=INT_MAX;
// 每条最短路径模拟前向再反向
void dfs(int last){temp.push_back(last);if(last==0){int need=0,back=0;for(int i=temp.size()-1;i>=0;i--){int tid=temp[i];if(num[tid]>=0){back+=num[tid];}else{ //够不够补再分情况讨论if(back>=(-num[tid])){ //够补back+=num[tid];}else{ //不够补，能分多少分多少need+=(-num[tid]-back);back=0;}}}// 根据题目这句话：Finally after another space, output the number of bikes that we must take back to PBMC after the condition of Sp is adjusted to perfect.if(minNeed>need){minNeed=need;minBack=back;res=temp;}else if(minNeed==need&&minBack>back){minBack=back;res=temp;}}for(int i=0;i<pre[last].size();i++){dfs(pre[last][i]);}temp.pop_back();
}int main(){scanf("%d%d%d%d",&cmax,&n,&sp,&m);graph.resize(n+1);num.resize(n+1,0);pre.resize(n+1);dis.resize(n+1,INT_MAX);dis[0]=0;for(int i=1;i<=n;i++){scanf("%d",&num[i]);num[i]-=(cmax/2);}for(int i=0;i<m;i++){int s,d,w;scanf("%d%d%d",&s,&d,&w);graph[s].push_back(make_pair(d,w));graph[d].push_back(make_pair(s,w));}priority_queue<ipair, vector<ipair>, greater<ipair>> pq;pq.push(make_pair(0,0)); //weight, pointwhile(!pq.empty()){int u=pq.top().second;pq.pop();if(u==sp) break;for(auto& it:graph[u]){int v=it.first;int weight=it.second;if(dis[u]+weight<dis[v]){dis[v]=dis[u]+weight;pre[v].clear();pre[v].push_back(u);pq.push(make_pair(dis[v],v));}else if(dis[u]+weight==dis[v]){pre[v].push_back(u);}}}dfs(sp);printf("%d ",minNeed);for(int i=res.size()-1;i>=0;i--){printf(i==0?"%d":"%d->",res[i]);}printf(" %d",minBack);
}