#include<bits/stdc++.h>
using namespace std;
const int inf = 1e9;
int sum,n,tar,m;
int num[507];
int edge[507][507];
int u,v,val;
int mn=inf,mn_send=inf,mn_back=inf;
int cur=0,cur_send=0,cur_back=0;
int vis[507];
vector<int>cur_path,ans;
void dfs(int x){
if(cur>mn)//已经不是最短路，无需深入了
return;
if(x==tar){//到达目标点，有更优解就更新
if(cur<mn){
mn=cur;
mn_send=cur_send;
mn_back=cur_back;
ans=cur_path;
}
else if(cur==mn&&(cur_send<mn_send||cur_send==mn_send&&cur_back<mn_back)){
mn_send=cur_send;
mn_back=cur_back;
ans=cur_path;
}
return;
}
for(int i=1;i<=n;++i){
if(vis[i]||edge[x][i]==inf)//前面已经经过该点或者此路不通就换下一个点
continue;
vis[i]=1;
cur_path.push_back(i);//放进路径中
cur+=edge[x][i];//修改当前路径长度
int tmp_send=cur_send;//存放当前需要发出
int tmp_back=cur_back;//存放当前需要返回
if(num[i]+cur_back<sum/2)//如果当前站缺车
cur_send+=sum/2-num[i]-cur_back,cur_back=0;
else//当前站不缺车
cur_back+=num[i]-sum/2;
dfs(i);//在这个点的基础上接着深入
cur_path.pop_back();//还原到没有经过i点之前的状态
vis[i]=0;
cur-=edge[x][i];
cur_send=tmp_send;
cur_back=tmp_back;
}
}
int main(){
std::ios::sync_with_stdio(false);//关闭同步
cin>>sum>>n>>tar>>m;
for(int i=0;i<=n;++i)
for(int j=0;j<=n;++j)
edge[i][j]=inf,edge[j][i]=inf;//初始化让所有点之间路径无限长
for(int i=1;i<=n;++i)
cin>>num[i];
for(int i=1;i<=m;++i){
cin>>u>>v>>val;
edge[u][v]=val;
edge[v][u]=val;
}
dfs(0);//从根节点开始深度优先搜索
cout<<mn_send<<" 0";
for(auto&it:ans)
cout<<"->"<<it;
cout<<" "<<mn_back;
return 0;
}
Public Bike Management (30)（DFS，VRCTOR，模拟）（PAT甲级）
原文：https://www.cnblogs.com/ldudxy/p/10797655.html