【PAT甲级】1018 Public Bike Management (30 分)（DFS，SPFA）
代码：
#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;
}
/*#include<bits/stdc++.h>
using namespace std;
const int maxn = 507;
const int INF = 1e9;
typedef struct node{
int v,l;
};
vector<node>adj[maxn];// 邻接表
int bike[maxn];//存储每个站点现有自行车数
int c,n,s,m;// 最大容量、站点数、问题站点编号、道路数
vector<int>pre[maxn];// 前驱结点数组
int d[maxn];//源点到各点的距离
int inq[maxn];//是否在队列中
vector<int>tempPath,path;//路径记录
int sent=INF,take=INF;// 派送数，回收数
void SPFA(){// 由于不存在负边，所以无需判断负环（最短路一定存在时可以使用SPFA，效率不错）
queue<int>q;
for(int i=1;i<=n;++i)//初始化距离
d[i]=INF;
d[0]=0;
q.push(0);
inq[0]=1;
while(!q.empty()){
int u=q.front();
q.pop();
inq[u]=0;
for(int i=0;i<adj[u].size();++i){
int v=adj[u][i].v;
int l=adj[u][i].l;
if(!v)
continue;
if(d[u]+l<d[v]){//松弛
d[v]=d[u]+l;
pre[v].clear();//最短距离减小需要先清空前驱结点
pre[v].push_back(u);
if(!inq[v]){
q.push(v);
inq[v]=1;
}
}
else if(d[u]+l==d[v])// 距离相等，只要增加前驱结点
pre[v].push_back(u);
}
}
}
void DFS(int x){
if(!x){//走回根结点，更新答案
int remain=0,tempSent=0;//记录处理完第i个站点时多出的自行车数量，和已经派送的自行车数量
tempPath.push_back(x);
for(int i=tempPath.size()-2;i>=0;--i){//遍历路径
int u=tempPath[i];
remain=remain+bike[u]-c/2;//更新剩余数量
if(remain<0){//剩余数量小于0
tempSent-=remain;//当前站点需要派送
remain=0;//剩余数量重置为0
}
}
if(tempSent<sent){//第二优先级，派送数量少
path=tempPath;
sent=tempSent;
take=remain;
}
else if(tempSent==sent&&remain<take){//第三优先级，回收数量少
path=tempPath;
take=remain;
}
tempPath.pop_back();
}
tempPath.push_back(x);
for(int i=0;i<pre[x].size();++i)//处理所有可能的前驱结点
DFS(pre[x][i]);
tempPath.pop_back();
}
int main(){
int s1,s2,t;
scanf("%d%d%d%d",&c,&n,&s,&m);
for(int i=1;i<=n;++i)
scanf("%d",&bike[i]);
for(int i=0;i<m;++i){
scanf("%d%d%d",&s1,&s2,&t);
node x;
x.v=s2;
x.l=t;
node y;
y.v=s1;
y.l=t;
adj[s1].push_back(x);
adj[s2].push_back(y);
}
SPFA();
DFS(s);
printf("%d ",sent);
for(int i=path.size()-1;i>=0;--i){
if(i<path.size()-1)
printf("->");
printf("%d",path[i]);
}
printf(" %d",take);
return 0;
}*/
//SPFA先处理单源最短路，然后对最短路进行DFS