이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int inf = 1e9 + 7;
const ll infll = 1e18;
template<typename T>
istream &operator>>(istream &is, vector<T> &a) {
for (auto &i : a) {
is >> i;
}
return is;
}
struct Edge {
int to, w;
};
vector<vector<Edge>> dag;
vector<ll> da, db;
vector<ll> dp_a, dp_b;
vector<bool> used;
ll ans = infll;
void dfs(int v) {
used[v] = 1;
dp_a[v] = da[v];
dp_b[v] = db[v];
for (auto [u, w] : dag[v]) {
if (!used[u]) {
dfs(u);
}
dp_a[v] = min(dp_a[v], dp_a[u]);
dp_b[v] = min(dp_b[v], dp_b[u]);
}
ans = min(ans, dp_a[v] + db[v]);
ans = min(ans, dp_b[v] + da[v]);
}
int32_t main() {
#ifdef LOCAL
freopen("/tmp/input.txt", "r", stdin);
#else
ios::sync_with_stdio(false);
cin.tie(nullptr);
#endif
int n, m;
cin >> n >> m;
int s, t, a, b;
cin >> s >> t >> a >> b;
--s, --t, --a, --b;
vector<vector<Edge>> g(n);
for (int i = 0; i < m; ++i) {
int u, v, w;
cin >> u >> v >> w;
--u, --v;
g[u].push_back({v, w});
g[v].push_back({u, w});
}
auto dijkstra = [&](int s) {
vector<ll> dp(n, infll);
dp[s] = 0;
using pii = pair<ll, int>;
priority_queue<pii, vector<pii>, greater<pii>> pq;
pq.push({dp[s], s});
while (!pq.empty()) {
auto [_, v] = pq.top();
pq.pop();
if (_ > dp[v]) {
continue;
}
for (auto [u, w] : g[v]) {
if (dp[u] > dp[v] + w) {
dp[u] = dp[v] + w;
pq.push({dp[u], u});
}
}
}
return dp;
};
vector<ll> ds = dijkstra(s);
vector<ll> dt = dijkstra(t);
dag.resize(n);
for (int i = 0; i < n; ++i) {
for (auto [j, w] : g[i]) {
if (ds[i] + w + dt[j] == ds[t]) {
dag[i].push_back({j, w});
}
}
}
da = dijkstra(a);
db = dijkstra(b);
dp_a.resize(n);
dp_b.resize(n);
used.resize(n);
ans = da[b];
dfs(s);
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... |