思路：你的答案必须满足三个条件：
1.在所有路径中选择最短的；
2.如果路径相等，则选择从PBMC中送出最少的；
3.如果路径相等且PBMC送出的车也相等，则选择带回最少的。
注意：这题很恶心，你要考虑–在最后计算发车数和返回车数时，首先要从sp开始反向寻找第一个缺车的站（由于发车是单向的，路径上靠近PBMC的站可以将多出的车交给较远的缺车的站，但较远的站之后不能将多出的车返还给较近的缺车站，其后多出的车最后全部返还给PBMC了，因此发车数要从第一个缺车的站开始往前计算），之后多出的车全部计入返回车辆数
AC代码
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define inf 0x3f3f3f3f
const int maxn = 500+5;
int c, m, n, goal;
int G[maxn][maxn], sta[maxn];
int vis[maxn];
int path[maxn], length, tmp[maxn];
struct res{
int length, send, back;
res() {
this->length = inf;
this->send = inf;
this->back = inf;
}
res(int l, int s, int b) {
this->length = l;
this->send = s;
this->back = b;
}
}ans;
void updatePath(int cnt) {
length = cnt;
for(int i = 0; i < cnt; i++) {
path[i] = tmp[i];
}
}
/*
1.在所有路径中选择最短的；
2.如果路径相等，则选择从PBMC中送出最少的；
3.如果路径相等且PBMC送出的车也相等，则选择带回最少的。
*/
res better(res &a, res &b, int cnt) {
bool update = false;
if(a.length > b.length) {
update = true;
} else if(a.length == b.length){
if(a.send > b.send) {
update = true;
} else if(a.send == b.send) {
if(a.back > b.back) {
update = true;
}
}
}
if(update) {
updatePath(cnt);
return b;
} else {
return a;
}
}
void dfs(int u, int len, int cnt, int send, int back) {
if(len > ans.length) return;
if(u == goal) {
res tp = res(len, send, back);
ans = better(ans, tp, cnt);
return;
}
for(int i = 1; i <= n; i++) {
if(!vis[i] && G[u][i] != -1) {
vis[i] = 1;
tmp[cnt] = i;
if(sta[i] >= c/2) {
dfs(i, len+G[u][i], cnt+1, send, back+sta[i]-c/2);
} else {
int x = c/2 - sta[i];
dfs(i, len+G[u][i], cnt+1, x>back?send+x-back:send, x>back?0:back-x);
}
vis[i] = 0;
}
}
}
void init() {
ans.length = inf;
ans.send = inf;
ans.back = inf;
memset(G, -1, sizeof(G));
memset(vis, 0, sizeof(vis));
}
int main() {
while(scanf("%d%d%d%d", &c, &n, &goal, &m) == 4) {
init();
for(int i = 1; i <= n; i++) {
scanf("%d", &sta[i]);
}
int u, v, cost;
for(int i = 0; i < m; i++) {
scanf("%d%d%d", &u, &v, &cost);
G[u][v] = cost;
G[v][u] = cost;
}
vis[0] = 1;
dfs(0, 0, 0, 0, 0);
printf("%d ", ans.send);
printf("0");
for(int i = 0; i < length; i++) {
printf("->%d", path[i]);
}
printf(" %d\n", ans.back);
}
return 0;
}如有不当之处欢迎指出！