题意：
每个自行车车站的最大容量为一个偶数cmax，如果一个车站里面自行车的数量恰好为cmax / 2，那么称处于完美状态。如果一个车展容量是满的或者空的，控制中心（处于结点0处）就会携带或者从路上手机一定数量的自行车前往该车站，一路上会让所有的车展沿途都达到完美。现在给出cmax，车站的数量n，问题车站sp，m条边，还有距离，求最短路径。如果最短路径有多个，求能带的最少的自行车数目的那条。如果还是有很多条不同的路，那么就找一个从车站带回的自行车数目最少的。带回的时候是不调整的
思路：
这题的题意我一开始没读懂，一开始以为是终点容量只有0这种可能，所以一直在疑惑为什么会有带回的量，但实际也有可能终点是满的，这样可能从终点带回一定量。知道这点后就比较简单，就是先求出最短路径，然后用dfs从后往前遍历最短路径。
#include<string>
#include<cstdlib>
#include<vector>
#include<stack>
#include<queue>
#include<utility>
#include<map>
#include<cstdlib>
#include<stdio.h>
#include<algorithm>
#include<functional>
#include<iostream>
#define INF 0x6ffff
using namespace std;const int maxn = 505;
int n, m, c, s;
int weight[maxn];
int dis[maxn];
bool vis[maxn];
int edge[maxn][maxn];
vector<int> pre[maxn];
vector<int> path, tempPath;
int needMin = INF, backMin = INF;void dijkstra() {fill(vis, vis + maxn, true);fill(dis, dis + maxn, INF);dis[0] = 0;for (int i = 0; i <= n; i++) {int u = -1, min = INF;for (int j = 0; j <= n; j++) {if (vis[j] && min > dis[j]) {min = dis[j];u = j;}}vis[u] = false;for (int v = 0; v <= n; v++) {if (vis[v] && edge[u][v] != INF) {if (dis[v] > dis[u] + edge[u][v]) {dis[v] = dis[u] + edge[u][v];pre[v].clear();pre[v].push_back(u);}else if (dis[v] == dis[u] + edge[u][v]) {pre[v].push_back(u);}}}}
}void dfs(int v) {tempPath.push_back(v);if (v == 0) {int need = 0, back = 0;for (int i = tempPath.size() - 1; i >= 0; i--) {int id = tempPath[i];if (weight[id] > 0)back += weight[id];else {if (back > (0 - weight[id])) back += weight[id];else { //只有back比要给的车数少时才计算needneed += ((0 - weight[id]) - back);back = 0;}}}if (need < needMin) {needMin = need;backMin = back;path = tempPath;}else if (need == needMin&&back < backMin) {backMin = back;path = tempPath;}tempPath.pop_back();return;}for (int i = 0; i < pre[v].size(); i++) dfs(pre[v][i]);tempPath.pop_back();
}int main() {cin >> c >> n >> s >> m;for (int i = 1; i <= n; i++) {cin >> weight[i];weight[i] -= c / 2;}fill(edge[0], edge[0] + maxn*maxn, INF);while (m--) {int u, v, e;cin >> u >> v >> e;edge[u][v] = edge[v][u] = e;}dijkstra();dfs(s);printf("%d 0", needMin);for (int i = path.size() - 2; i >= 0; i--) {printf("->%d", path[i]);}printf(" %d", backMin);return 0;
}