和 1475. 紧急情况 - 题解 一样, 不过这次要统计的信息为可能路径的 边累计权值 和 具体路径
边累计权值参考 map<pair<int, int>, int>
记录的边权
具体路径 使用 deque
记录, 递归时头插结点
#include <iostream>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <queue>
#include <deque>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <array>
#include <string>
#include <vector>
#include <stack>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <climits>
#include <functional>
#include <iterator>
using namespace std;
#ifdef DEBUG
#define cin MyIStream
ifstream MyIStream{"../../data", ios::in};
#endif
template<typename T>
string fmt_seq_container(T const &seq_container, string const &join = " ") {
ostringstream s;
auto seq_begin = begin(seq_container);
auto sz = end(seq_container) - seq_begin;
if (sz) {
s << *(seq_begin++);
while (--sz) s << join << *(seq_begin++);
}
return s.str();
}
using ll = long long;
struct ENode {
int to, ne, w;
};
vector<int> head, dis, vis;
vector<ENode> edges;
vector<vector<int> > pre;
map<pair<int, int>, int> cost;
constexpr auto MAX_DIS = numeric_limits<decltype(dis)::value_type>::max();
template<typename T>
void add_edge(int u, int v, T w = 0) {
edges.push_back({v, head[u], w});
head[u] = edges.size() - 1;
}
int N, M, S, D;
vector path_v{0};
vector<deque<int> > path{{}};
void dfs(int u, int path_id) {
if (u == S) {
path[path_id].push_back(D);
return;
};
auto const &pres = pre[u];
auto cur_path_v = path_v[path_id];
auto cur_path = path[path_id];
path_v[path_id] = cur_path_v + cost[{u, pres[0]}];
path[path_id].push_front(pres[0]);
dfs(pres[0], path_id);
for (int i = 1; i < pres.size(); i++) {
path_v.push_back(cur_path_v + cost[{u, pres[i]}]);
path.push_back(cur_path);
path[path_v.size() - 1].push_front(pres[i]);
dfs(pres[i], path_v.size() - 1);
}
}
int main() {
fstream::sync_with_stdio(false);
cin >> N >> M >> S >> D;
head = vector(N, -1);
dis = vector(N, MAX_DIS);
vis = vector(N, 0);
pre = vector(N, vector<int>{});
while (M--) {
int a, b, c, d;
cin >> a >> b >> c >> d;
add_edge(a, b, c);
add_edge(b, a, c);
cost[{a, b}] = cost[{b, a}] = d;
}
using spnode_t = pair<int, int>;
priority_queue<spnode_t, vector<spnode_t>, greater<> > q;
q.emplace(0, S);
while (!q.empty()) {
auto [udis, u] = q.top();
q.pop();
if (vis[u]) continue;
vis[u] = 1;
for (int j = head[u]; ~j; j = edges[j].ne) {
int v = edges[j].to, w = edges[j].w;
if (dis[v] >= udis + w) {
if (dis[v] > udis + w) pre[v].clear();
dis[v] = udis + w;
if (v != S) pre[v].emplace_back(u);
q.emplace(dis[v], v);
}
}
}
dfs(D, 0);
auto min_cost_path_id = min_element(path_v.begin(), path_v.end()) - path_v.begin();
cout << fmt_seq_container(path[min_cost_path_id]) << " "
<< dis[D] << " "
<< path_v[min_cost_path_id] << endl;
return 0;
}