[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;
}