题目链接：点击打开链接
题目大意：每个自行车车站的最大容量为一个偶数cmax，如果一个车站里面自行车的数量恰好为cmax / 2，那么称处于完美状态。如果一个车站容量是满的或者空的，控制中心（处于结点0处）就会携带或者从路上收集一定数量的自行车前往该车站，一路上会让所有的车站沿途都达到完美。现在给出cmax，车站的数量n，问题车站sp，m条边，还有距离，求最短路径。如果最短路径有多个，求能带的最少的自行车数目的那条。如果还是有很多条不同的路，那么就找一个从车站带回的自行车数目最少的。带回的时候是不调整的。
解题思路：Dijkstra + DFS。如果只有Dijkstra是不可以的，因为minNeed和minBack在路径上的传递不满足最优子结构，不是简单的相加的过程，只有在所有路径都确定了之后才能区选择最小的need和最小的back。
Dijkstra求最短路径，dfs求minNeed和minBack和最终path，dfs的时候模拟一遍需要调整的过程，求出最后得到的need和back，与minNeed和minBack比较然后根据情况更新path，最后输出 minNeed path 和 minBack，记得path是从最后一个结点一直到第一个结点的，所以要倒着输出。
AC 代码
usingnamespacestd; typedeflonglongll; constintmaxn=520; intn,mined,mibak; intwrr[maxn], vis[maxn], dis[maxn]; intg[maxn][maxn]; vector<int>pre[maxn], tpath, path; voidinit() { mined=mibak=INF; mem(dis,INF); mem(g,INF); mem(vis,0); mem(wrr,0); } intdijkstra(ints) { dis[s]=0; while(1) { intmi=INF; s=-1; for(inti=0;i<=n;i++) if(!vis[i] &&dis[i]<mi) mi=dis[i], s=i; if(s==-1) return0; vis[s]=1; for(inti=0;i<=n;i++) { if(!vis[i] &&mi+g[s][i]<dis[i]) { dis[i]=mi+g[s][i]; pre[i].clear(); pre[i].push_back(s); } elseif(!vis[i] &&dis[i]==mi+g[s][i]) pre[i].push_back(s); } } } voiddfs(ints) { tpath.push_back(s); if(0==s) { intned=0, bak=0; for(inti=tpath.size()-1;i>=0;i--) { intu=tpath[i], w=wrr[u]; if(w>0) bak+=w; else { if(bak>-w) bak+=w; else { ned+=-w-bak; bak=0; } } } if(ned<mined) { mined=ned; mibak=bak; path=tpath; } elseif(ned==mined&&bak<mibak) { mibak=bak; path=tpath; } tpath.pop_back(); return; } for(inti=0;i<pre[s].size();i++) dfs(pre[s][i]); tpath.pop_back(); } intmain() { init(); intcmax,m,w,u,v,sp; scanf("%d%d%d%d",&cmax,&n,&sp,&m); for(inti=1;i<=n;i++) scanf("%d",&wrr[i]), wrr[i]=wrr[i]-cmax/2; for(inti=0;i<m;i++) scanf("%d%d%d",&u,&v,&w), g[u][v]=g[v][u]=w; dijkstra(0); dfs(sp); printf("%d ",mined); for(inti=path.size()-1;i>=0;i--) printf("%d%s",path[i],i==0?"":"->"); printf(" %d\n",mibak); return0; }
