（不满足最优子问题，所以不能直接用Dijkstra求解）
细节：vector 数组可以整体赋值哦！
fill()函数二维数组起始地址edge[0]而不是edge,头文件algorithm
题目大意：每个自行车车站的最大容量为一个偶数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是从最后一个结点一直到第一个结点的，所以要倒着输出～
#include<stdio.h>
#include<vector>
#include<algorithm>
#pragma warning(disable:4996)
#define INF 0xfffffff
using namespace std;
int cmax, n, m, sp;
int d[510], vis[510], bike[510];
int edge[510][510];
vector<int>res, tmp, pre[510];
int minback =INF, minsend=INF;
void dfs(int v)
{
tmp.push_back(v);
if (0 == v) {
int back = 0, send = 0;
for (int i = tmp.size() - 1; i >= 0; i--) {
if (bike[tmp[i]] > 0) {
back += bike[tmp[i]];
}
else {
if (back > (0 - bike[tmp[i]])) {
back += bike[tmp[i]];
}
else {
send += (0 - bike[tmp[i]] - back);
back = 0;
}
}
}
if (send < minsend) {
minsend = send;
minback = back;
res = tmp;
}
else if (send == minsend && back < minback) {
minback = back;
res = tmp;
}
tmp.pop_back();
return;
}
for (int i = 0; i < pre[v].size(); i++)
dfs(pre[v][i]);
tmp.pop_back();
}
int main()
{
fill(edge[0],edge[0]+510*510,INF);
fill(d, d + 510, INF);
scanf("%d%d%d%d",&cmax,&n,&sp,&m);
for (int i = 1; i <= n; i++) {
scanf("%d", &bike[i]), bike[i] -= cmax / 2;
}
for (int i = 1,a,b,c; i <= m; i++) {
scanf("%d%d%d", &a, &b,&c);
edge[a][b] = edge[b][a] = c;
}
d[0] = 0;
for (int i = 0; i <= n; i++) {
int u = -1, min = INF;
for (int j = 0; j <= n; j++) {
if (0 == vis[j] && d[j] < min) {
u = j; min = d[j];
}
}
if (-1 == u) break;
vis[u] = 1;
for (int v = 0; v <= n; v++) {
if (0 == vis[v] && edge[u][v] != INF) {
if (d[v] > d[u] + edge[u][v]) {
d[v] = d[u] + edge[u][v];
pre[v].clear();
pre[v].push_back(u);
}
else if (d[v] == d[u] + edge[u][v]) {
pre[v].push_back(u);
}
}
}
}
dfs(sp);
printf("%d ",minsend);
int i = res.size() - 1;
for (; i > 0; i--){
printf("%d->", res[i]);
}
printf("%d ", res[i]);
printf("%d", minback);
getchar();
getchar();
return 0;
}
1018 Public Bike Management -PAT甲级真题（Dijkstra+DFS）
原文：https://www.cnblogs.com/zxzmnh/p/11628551.html