题目
解决
思路
Dijkstra+DFS在输入的时候，就将每个站点需要调整的数量，计算出来注意PBMC编号是0，站点编号为1~N规则：
最短路径PBMC出发的车辆最少回到PBMC的车辆最少
实现
Code1
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int N = 510;
const int INF = 1000000000;
int cmax, n, m, sp;
int G[N][N];
int d[N];
int c[N];
bool vis[N] = {false};
vector<int> pre[N];
vector<int> path, tempPath;
int minSend = INF, minRemain = INF;
void Dijkstra(int s){
fill(d, d+N, INF);
d[s] = 0;
for(int i=0; i<=n; i++){
int u = -1;
int MIN = INF;
for(int j=0; j<=n; j++){
if(vis[j] == false && d[j] < MIN){
u = j;
MIN = d[j];
}
}
if(u == -1) return;
vis[u] = true;
for(int v=0; v<=n; v++){
if(vis[v] == false && G[u][v] != INF){
if(d[u] + G[u][v] < d[v]){
d[v] = d[u] + G[u][v];
pre[v].clear();
pre[v].push_back(u);
}else if(d[u] + G[u][v] == d[v]){
pre[v].push_back(u);
}
}
}
}
}
void DFS(int v){
if(v == 0){
tempPath.push_back(v);
int send = 0, remain = 0;
for(int i=tempPath.size()-1; i>=0; i--){
int id = tempPath[i];
if(c[id] > 0){//带走车
remain += c[id];
}else{//留下车
if(remain > abs(c[id])){
remain -= abs(c[id]);
}else{
send += abs(c[id]) - remain;
remain = 0;
}
}
}
if(send < minSend){
minSend = send;
minRemain = remain;
path = tempPath;
}else if(send == minSend && remain < minRemain){
minRemain = remain;
path = tempPath;
}
tempPath.pop_back();
return;
}
tempPath.push_back(v);
for(int i=0; i<pre[v].size(); i++){
DFS(pre[v][i]);
}
tempPath.pop_back();
}
int main(){
scanf("%d%d%d%d", &cmax, &n, &sp, &m);
for(int i=1; i<=n; i++){
scanf("%d", &c[i]);
c[i] -= cmax / 2; //需要补充或者带走的车辆数
}
int u, v;
fill(G[0], G[0]+N*N, INF);
for(int i=0; i<m; i++){
scanf("%d%d", &u, &v);
scanf("%d", &G[u][v]);
G[v][u] = G[u][v];
}
Dijkstra(0); //0是PBMC
DFS(sp);
printf("%d ", minSend);
for(int i=path.size()-1; i>=0; i--){
printf("%d", path[i]);
if(i > 0) printf("->");
}
printf(" %d", minRemain);
return 0;
}
