이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)x.size()
#define getBit(x, i) ((x) >> (i) & 1)
#define rep(i, begin, end) for (ll i = (begin); i <= (end); i++)
#define rrep(i, begin, end) for (ll i = (begin); i >= (end); i--)
typedef long long ll;
typedef pair<ll, ll> ii;
template <class T>
bool minimize(T &a, const T &b) {
if(a > b) {a = b; return 1;}
return 0;
}
template <class T>
bool maximize(T &a, const T &b) {
if(a < b) {a = b; return 1;}
return 0;
}
const int N = 1e5 + 7;
int n, m, s, t, x, y;
bool done[N];
ll d[N][4], f[N], ans = 1e18;
vector<ii> adj[N];
vector<int> dag[N];
void dijk(int s, int i) {
priority_queue<ii, vector<ii>, greater<ii>> pq;
pq.push(ii(0, s)); d[s][i] = 0;
while (sz(pq)) {
ii u = pq.top(); pq.pop();
if (u.fi != d[u.se][i]) continue;
for (auto [v, w]: adj[u.se]) {
if (minimize(d[v][i], d[u.se][i] + w)) {
pq.push(ii(d[v][i], v));
}
}
}
}
void dfs1(int u) {
done[u] = 1; f[u] = d[u][3]; // shortest path from y->u
for (auto [v, w]: adj[u]) if (d[u][0] + d[v][1] + w == d[t][0]) {
if (!done[v]) dfs1(v);
minimize(f[u], f[v]);
}
minimize(ans, d[u][2] + f[u]);
}
void dfs2(int u) {
done[u] = 1; f[u] = d[u][3]; // shortest path from y->u
for (auto [v, w]: adj[u]) if (d[u][1] + d[v][0] + w == d[t][0]) {
if (!done[v]) dfs2(v);
minimize(f[u], f[v]);
}
minimize(ans, d[u][2] + f[u]);
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> m >> s >> t >> x >> y;
rep(i, 1, m) {
int u, v, w;
cin >> u >> v >> w;
adj[u].pb(ii(v, w)); adj[v].pb(ii(u, w));
}
memset(d, 0x3f, sizeof d);
dijk(s, 0); dijk(t, 1); dijk(x, 2); dijk(y, 3);
ans = d[y][2];
memset(f, 0x3f, sizeof f);
dfs1(s);
memset(done, 0, sizeof done);
memset(f, 0x3f, sizeof f);
dfs2(t);
cout << ans;
}
# | 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... |