分析

$Dij + DFS$

i: 从PBMC出发到终点的一条最优路径上, 必须路过一个结点调整一个结点。

具体调整方式如下：

1、若该结点大于$Cmax$ / $2$：就收集该结点上多余的自行车

2、若该结点小于$Cmax$ / $2$：就从源点到该结点的路径上已收集到的自行车中补。

3、若不够补，首先把收集到的自行车全部补上，再缺的从$PBMC$中拿，把收集到的自行车数量置$0$

ii: 上述收集和剩余的自行车在区间上不满足最优子结构, 尽量用$Dij+DFS$

1、在已经搜索到一条路径后，需要倒着枚举所有结点，因为只在去的路上调整，回来不调整

处理输入点权的时候，最好把点权直接减去$Cmax$ / $2$,判定方便

C++ 代码

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 510, INF = 0x3fffffff;

int g[N][N];
int dist[N], bike[N]; // 节点的自行车数量
vector<int> pre[N];
vector<int> path, temp;
bool st[N];
int n, m, Cmax, ed, minNeed = INF, minRemain = INF;

//每个节点可以贡献的自行车数量为 max(bike[i]-Cmax/2,0)
void dij(){
    memset(dist, 0x3f, sizeof dist);
    dist[0] = 0;

    for(int i = 1; i <= n; ++ i )
    {
        int t = -1;
        for(int j = 0; j <= n; j ++ )
        {
            if(!st[j] && (t == -1 || dist[j] < dist[t])) t = j;
        }
        if(t == -1) return;
        st[t] = true;
        for(int j = 0; j <= n; ++ j )
        {
            if(dist[j] > dist[t] + g[t][j])
            {
                dist[j] = dist[t] + g[t][j];
                pre[j].clear();
                pre[j].push_back(t);
            }
            else if(dist[j] == dist[t] + g[t][j]) pre[j].push_back(t);
        }
    }
}
void dfs(int u){
    if(u == 0){
        temp.push_back(u);
        int need = 0, remain = 0;
        for(int i = temp.size() - 1; i >= 0; i -- ){
            int id = temp[i];
            if(bike[id] > 0) remain += bike[id];
            else{
                if(remain > abs(bike[id])) remain -= abs(bike[id]);
                else{
                    need += abs(bike[id]) - remain;
                    remain = 0;
                }
            }
        }
        if(need < minNeed){
            minNeed = need;
            path = temp;
            minRemain = remain;
        }
        else if(need == minNeed && remain < minRemain){
            path = temp;
            minRemain = remain;
        }
        temp.pop_back();
        return;
    }
    temp.push_back(u);
    for(int i = 0; i < pre[u].size(); ++ i ){
        dfs(pre[u][i]);
    }
    temp.pop_back();
}
int main(){
    memset(g, 0x3f, sizeof g);
    cin >> Cmax >> n >> ed >> m;

    for(int i = 1; i <= n; ++ i ) {
        cin >> bike[i];
        bike[i] -= Cmax / 2;
    }

    for(int i = 0; i < m; ++ i ){
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = g[b][a] = min(g[a][b], c);
    }
    dij();
    dfs(ed);

    cout << minNeed << " ";

    for(int i = path.size() - 1; i >= 0; i -- )
    {
        printf("%d",path[i]);
        if(i != 0) printf("->");
        else printf(" ");
    }
    cout << minRemain;
    return 0;
}