이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define dbg(x) cerr << #x << ": " << x << endl;
const ll INF = 1e18;
const int MAX_N = 1e5 + 5;
vector<pair<int, int>> g[MAX_N];
vector<int> new_g[MAX_N];
ll dp[2][MAX_N];
ll dist[4][MAX_N];
void dfs_order(int v, vector<int>& order, vector<bool>& used) {
used[v] = true;
for (auto u : new_g[v]) {
if (!used[u]) {
dfs_order(u, order, used);
}
}
order.push_back(v);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
int s1, t1;
cin >> s1 >> t1;
--s1, --t1;
int s2, t2;
cin >> s2 >> t2;
--s2, --t2;
vector<tuple<int, int, int>> edges(m);
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
--u, --v;
int w;
cin >> w;
g[u].emplace_back(v, w);
g[v].emplace_back(u, w);
edges[i] = {u, v, w};
}
{
array<int, 4> start_vertices = {s2, t2, s1, t1};
for (int i = 0; i < 4; ++i) {
int s = start_vertices[i];
fill_n(dist[i], n, INF);
vector<bool> used(n);
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
pq.emplace(0, s);
while (!pq.empty()) {
auto [curr_dist, v] = pq.top();
pq.pop();
if (used[v]) continue;
used[v] = true;
dist[i][v] = curr_dist;
for (const auto& [u, w] : g[v]) {
if (used[u] || curr_dist + w >= dist[i][u]) continue;
dist[i][u] = curr_dist + w;
pq.emplace(dist[i][u], u);
}
}
}
}
{
for (auto [u, v, w] : edges) {
for (int t = 0; t <= 1; ++t) {
if (dist[2][u] + w == dist[2][v] && dist[2][v] + dist[3][v] == dist[2][t1]) {
new_g[u].push_back(v);
}
swap(u, v);
}
}
}
vector<int> order;
{
vector<bool> used(n);
dfs_order(s1, order, used);
reverse(order.begin(), order.end());
}
fill_n(dp[0], n, INF);
fill_n(dp[1], n, INF);
ll ans = dist[0][t2];
for (auto v : order) {
for (int t = 0; t <= 1; ++t) {
dp[t][v] = min(dp[t][v], dist[t][v]);
for (auto u : new_g[v]) {
dp[t][u] = min(dp[t][u], dp[t][v]);
}
ans = min(ans, dp[t][v] + dist[t ^ 1][v]);
}
}
cout << ans << '\n';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |