本题是一道spfa+dfs题，难点在于不能在spfa的过程中计算答案，而要计算完所有最短路径之后再进行计算。
我做完这道题之后，一直卡在25分，百思不得其解，后来发现居然是题意又理解错了。以后面对英文题目要加倍细心。
这道题是我做的第二道spfa模版题，下一道题我决定采用dijskra，两种方法轮流练习熟练。
#include <iostream>
#include<vector>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<map>
#include<cstdlib>
#include<queue>
#include<cstring>
#include<set>
using namespace std;
int cmax,n,sp,m;
int c[520];
int in[520]={0};//节点是否在队列中
int dis[520];
queue<int>q;
set<int>pre[520];//每个节点的前驱节点
struct Node
{int v;int w;int u;Node(int _u,int _v,int _w):u(_u),v(_v),w(_w){}
};
vector<Node>a[520];
vector<Node>b[520];
vector<int>ans;
vector<int>outPutAns;
int bikes=0x3f3f3f3f;
int leftBikes=0x3f3f3f3f;
void dfs(int head)
{ans.push_back(head);if(head==0){int curBikes=0;int curTakebikes=0;for(int i=ans.size()-2;i>=0;i--){if(c[ans[i]]>cmax/2){curBikes+=c[ans[i]]-cmax/2;}else if(c[ans[i]]<=cmax/2){int delta=cmax/2-c[ans[i]];if(curBikes<delta){curTakebikes+=delta-curBikes;curBikes=0;}else{curBikes-=delta;}}}if(curTakebikes<bikes){bikes=curTakebikes;leftBikes=curBikes;outPutAns=ans;}else if(curTakebikes==bikes&&curBikes<leftBikes){bikes=curTakebikes;leftBikes=curBikes;outPutAns=ans;}ans.pop_back();return;}for(int i=0;i<b[head].size();i++){//cout<<"前驱节点："<<b[head][i].u<<endl;int u=b[head][i].u;int w=b[head][i].w;if(dis[u]+w==dis[head]){dfs(u);}}ans.pop_back();
}
int main()
{scanf("%d%d%d%d",&cmax,&n,&sp,&m);fill(dis+0,dis+n+1,0x3f3f3f3f);for(int i=1;i<=n;i++)scanf("%d",&c[i]);for(int i=1;i<=m;i++){int x,y,z;scanf("%d%d%d",&x,&y,&z);a[x].push_back(Node(x,y,z));a[y].push_back(Node(y,x,z));b[y].push_back(Node(x,y,z));b[x].push_back(Node(y,x,z));}dis[0]=0;in[0]=1;q.push(0);while(!q.empty()){int head=q.front();q.pop();in[head]=0;for(int i=0;i<a[head].size();i++){int v=a[head][i].v;int w=a[head][i].w;if(dis[v]>dis[head]+w){dis[v]=dis[head]+w;if(in[v]==0){in[v]=1;q.push(v);}}}}dfs(sp);cout<<bikes<<" ";cout<<outPutAns[outPutAns.size()-1];for(int i=outPutAns.size()-2;i>=0;i--){cout<<"->"<<outPutAns[i];}cout<<" ";cout<<leftBikes;}