이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
#define mp make_pair
#define f first
#define s second
using ll = long long;
using pi = pair<int, int>;
using C = array<ll, 2>;
template<class T> using pq = priority_queue<T, vector<T>, greater<T>>;
const ll INFL = ll(1e18) + 10;
int main() {
cin.tie(0)->sync_with_stdio(0);
int N, M; cin >> N >> M;
int S, T, U, V; cin >> S >> T >> U >> V; --S, --T, --U, --V;
vector<vector<pi>> adj(N);
for(int i = 0; i < M; i++) {
int u, v, w; cin >> u >> v >> w; --u, --v;
adj[u].push_back(mp(v, w));
adj[v].push_back(mp(u, w));
}
const int TIMES = 3;
vector<vector<ll>> dst(N, vector<ll>(TIMES, INFL));
vector<vector<int>> chd(N), ADJ(N), RADJ(N);
auto dijk = [&](int s, int t, bool CHD) {
vector<int> vis(N, 0);
dst[s][t] = 0;
pq<C> q; q.push(C{dst[s][t], s});
while(size(q) > 0) {
auto [d, u] = q.top(); q.pop();
// cout << d << " " << u << endl;
if (vis[u]) continue;
vis[u] = 1;
for(const auto &e : adj[u]) {
int v, w; tie(v, w) = e;
// cout << v << " - " << w << endl;
if (dst[v][t] > dst[u][t]+w) {
dst[v][t] = dst[u][t] + w;
q.push(C{dst[v][t], v});
if (CHD) chd[v] = {};
}
if (CHD && dst[v][t] == dst[u][t]+w) chd[v].push_back(u);
}
}
};
dijk(S, 0, 1);
dijk(U, 1, 0);
dijk(V, 2, 0);
function<void(int)> make = [&](int u) {
for(const auto &v : chd[u]) {
// cout << u << " " << v << nl;
ADJ[u].push_back(v);
RADJ[v].push_back(u);
make(v);
}
chd[u] = {};
};
make(T);
vector<array<ll, 2>> dp(N, {INFL, INFL}), rdp(N, {INFL, INFL}); // 0 -> U and 1 -> V
for(int i = 0; i < N; i++) dp[i] = {dst[i][1], dst[i][2]}, rdp[i] = {dst[i][1], dst[i][2]};
for(int t = 0; t < 2; t++) {
vector<int> in(N);
for(int u = 0; u < N; u++) for(auto v : ADJ[u]) in[v]++;
queue<int> q;
for(int u = 0; u < N; u++) if (in[u] == 0) q.push(u);
while(size(q) > 0) {
int u = q.front(); q.pop();
for(auto v : ADJ[u]) {
dp[v][0] = min(dp[v][0], dp[u][0]);
dp[v][1] = min(dp[v][1], dp[u][1]);
if (--in[v] == 0) q.push(v);
}
}
ADJ.swap(RADJ);
dp.swap(rdp);
}
ll ans = INFL;
for(int i = 0; i < N; i++) {
ans = min(ans, dp[i][0] + rdp[i][1]);
ans = min(ans, rdp[i][0] + dp[i][1]);
}
cout << ans << nl;
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... |