[Advanced/C++/1018] Suggestion

[xwcai98]

递归处理所有最短路的时候，计算带出自行车和带回自行车部分，有许多if else，代码很冗杂，本质上只要几行就够了，详见下面代码53-57行。另外一提，vector作为传参不失为好的办法。

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int cap, n, en, m;
    cin >> cap >> n >> en >> m;
    cap /= 2;
    vector<int> a(++n);
    for (int i = 1; i < n; ++i) {
        cin >> a[i];
        a[i] -= cap;
    }
    vector<vector<pair<int, int>>> adj(n);
    for (int i = 0, u, v, x; i < m; ++i) {
        cin >> u >> v >> x;
        adj[u].emplace_back(v, x);
        adj[v].emplace_back(u, x);
    }
    //dijkstra find shortest paths
    vector<int> dis(n, INT_MAX);
    vector<vector<int>> pre(n); // store shortest paths
    dis[0] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    q.push({0, 0});
    while (!q.empty()) {
        int now = q.top().second;
        q.pop();
        for (auto e : adj[now]) {
            int to, nxt_dis;
            tie(to, nxt_dis) = e;
            if (dis[to] > dis[now] + nxt_dis) {
                dis[to] = dis[now] + nxt_dis;
                q.push({dis[to], to});
                pre[to].clear();
                pre[to].push_back(now);
            }
            else if (dis[to] == dis[now] + nxt_dis) {
                pre[to].push_back(now);
            }
        }
    }
    // dfs find best path among shortest paths
    vector<int> path;
    int out = INT_MAX, bak = INT_MAX;
    function<void(int, vector<int>)> dfs = [&](int id, vector<int> tmp) {
        tmp.push_back(id);
        if (id == 0) {
            reverse(tmp.begin(), tmp.end());
            int tmp_out = 0, tmp_bak = 0;
            for (int i = 1; i < tmp.size(); ++i) {
                tmp_bak += a[tmp[i]];
                if (tmp_bak < 0) {
                    tmp_out -= tmp_bak;
                    tmp_bak = 0;
                }
            }
            if (tmp_out < out || (tmp_out == out && tmp_bak < bak)) 
                path = tmp, out = tmp_out, bak = tmp_bak;
            return;
        }
        for (auto e : pre[id]) 
            dfs(e, tmp);
    };
    dfs(en, {});
    cout << out << " 0";
    for (int i = 1; i < path.size(); ++i)
        cout << "->" << path[i];
    cout << ' ' << bak << '\n';
    return 0;
}