이 제출은 이전 버전의 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>>;
int stk[123];
long long read() {
char ch = getchar();
while (ch < '0' || ch > '9') {
ch = getchar();
}
long long v = 0;
while ('0' <= ch && ch <= '9') {
v = v * 10 + (int) (ch - '0');
ch = getchar();
}
return v;
}
void write(ll x) {
int len = 0;
while (x > 0) {
stk[len++] = x % 10;
x /= 10;
}
for (int i = len - 1; i >= 0; i--) {
putchar('0' + stk[i]);
}
if (len == 0) {
putchar('0');
}
putchar('\n');
}
const ll INFL = ll(1e18) + 10;
int main() {
cin.tie(0)->sync_with_stdio(0);
int N = read(), M = read();
int S = read()-1, T = read()-1, U = read()-1, V = read()-1;
vector<vector<pi>> adj(N);
for(int i = 0; i < M; i++) {
int u = read()-1, v = read()-1, w = read();
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) {
int u = q.top()[1]; 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]);
}
write(ans);
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... |