本题是DFS+dijkstra算法的典型应用题，做本题前，需要认真读完题目（注意输出要求也会给出相应的判断）因为带去自行车，和拿回来的动作的都是实时发生的，不能用简单的加减计算，所以采用的使DFS+dijkstra的算法。最后判断部分条件，又因为此时是一半的容量为基准，所以可以考虑开始就将容量除以二
#include<cstdio> #include<iostream> #include<vector> #include<cmath> const int maxn=1010; const int inf=0x3fffffff; using namespace std; int G[maxn][maxn],d[maxn], minneed=inf,minback=inf,n,m,ed,cmax,weight[maxn]; bool vis[maxn]={false}; vector<int> pre[maxn],path,temp; void dijkstra(int s) { fill(d,d+maxn,inf); d[s]=0; for(int i=0;i<=n;i++) { int min=inf,u=-1; for(int j=0;j<=n;j++) { if(vis[j]==false&&d[j]<min) { min=d[j]; u=j; } } if(u==-1)return; vis[u]=true; for(int v=0;v<=n;v++) { if(vis[v]==false&&G[u][v]!=inf) { if(G[u][v]+d[u]<d[v]) { pre[v].clear(); pre[v].push_back(u); d[v]=G[u][v]+d[u]; } else if(G[u][v]+d[u]==d[v]) { pre[v].push_back(u); } } } } } void DFS(int v) { if(v==0) { int need=0,back=0; temp.push_back(v); for(int i=temp.size()-1;i>=0;i--) { if(weight[temp[i]]>0) back+=weight[temp[i]]; else { if(back>abs(weight[temp[i]])) back=back-abs(weight[temp[i]]); else { need+=abs(weight[temp[i]])-back; back=0; } } } if(need<minneed) { minneed=need; minback=back; path=temp; } else if(need==minneed&&back<minback) { minback=back; path=temp; } temp.pop_back(); return; } temp.push_back(v); for(int i=0;i<pre[v].size();i++) { DFS(pre[v][i]); } temp.pop_back(); } int main() { int c1,c2,d; cin>>cmax>>n>>ed>>m; cmax/=2; for(int i=1;i<=n;i++) { scanf("%d",&weight[i]); weight[i]-=cmax; } fill(G[0],G[0]+maxn*maxn,inf); for(int i=0;i<m;i++) { scanf("%d %d %d",&c1,&c2,&d); G[c1][c2]=G[c2][c1]=d; } dijkstra(0); DFS(ed); printf("%d 0",minneed); for(int i=path.size()-2;i>=0;i--) { printf("->%d",path[i]); } printf(" %d",minback); }