이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
using namespace std;
const int inf = 1e18;
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, a, b, c, d;
cin >> n >> m >> a >> b >> c >> d;
vector<vector<pair<int, int>>> adj(n + 5);
while (m--) {
int u, v, w;
cin >> u >> v >> w;
adj[u].emplace_back(w, v);
adj[v].emplace_back(w, u);
}
/*
dijkstra dari a ke b
track back jalurnya
array boolean jalur optimal
dist[optimal] = min. dari c ke semua optimal
dijkstra multisource yaitu b dan semua nodes jalur optimal
problem: kalau jalur optimal lebih dari satu, mau pake yg mana
sol:
- dijkstra from d
- dilihat dist from c + dist from d paling minimal
*/
vector<int> dist(n + 5, inf);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
dist[a] = 0;
pq.emplace(dist[a], a);
while (!pq.empty()) {
int cur = pq.top().se, wei = pq.top().fi;
pq.pop();
if (wei > dist[cur]) {
continue;
}
for (auto &i : adj[cur]) {
if (dist[i.se] > dist[cur] + i.fi) {
dist[i.se] = dist[cur] + i.fi;
pq.emplace(dist[i.se], i.se);
}
}
}
vector<bool> opt(n + 5);
queue<int> q;
q.push(b);
while (!q.empty()) {
int bre = q.size();
set<int> st;
while (bre--) {
int cur = q.front();
q.pop();
opt[cur] = true;
for (auto &i : adj[cur]) {
if (dist[cur] == dist[i.se] + i.fi) {
st.insert(i.se);
}
}
}
for (auto &i : st) {
q.push(i);
}
}
// subsoal 1
if (a == c) {
for (int i = 1; i <= n; ++i) {
dist[i] = inf;
}
dist[d] = 0;
pq.emplace(dist[d], d);
while (!pq.empty()) {
int cur = pq.top().se, wei = pq.top().fi;
pq.pop();
if (wei > dist[cur]) {
continue;
}
for (auto &i : adj[cur]) {
if (dist[i.se] > dist[cur] + i.fi) {
dist[i.se] = dist[cur] + i.fi;
pq.emplace(dist[i.se], i.se);
}
}
}
int ans = inf;
for (int i = 1; i <= n; ++i) {
if (opt[i]) {
ans = min(ans, dist[i]);
}
}
cout << ans << '\n';
return 0;
}
for (int i = 1; i <= n; ++i) {
dist[i] = inf;
}
dist[c] = 0;
pq.emplace(dist[c], c);
while (!pq.empty()) {
int cur = pq.top().se, wei = pq.top().fi;
pq.pop();
if (wei > dist[cur]) {
continue;
}
for (auto &i : adj[cur]) {
if (dist[i.se] > dist[cur] + i.fi) {
dist[i.se] = dist[cur] + i.fi;
pq.emplace(dist[i.se], i.se);
}
}
}
int mn = inf;
for (int i = 1; i <= n; ++i) {
if (opt[i]) {
mn = min(mn, dist[i]);
}
}
for (int i = 1; i <= n; ++i) {
dist[i] = inf;
}
dist[c] = 0;
pq.emplace(dist[c], c);
// ===== INI SALAH cuz blm tentu dari node optimal ke node optimal lain bisa segitu =====
for (int i = 1; i <= n; ++i) {
if (opt[i]) {
dist[i] = mn;
pq.emplace(dist[i], i);
}
}
while (!pq.empty()) {
int cur = pq.top().se, wei = pq.top().fi;
pq.pop();
if (wei > dist[cur]) {
continue;
}
for (auto &i : adj[cur]) {
if (dist[i.se] > dist[cur] + i.fi) {
dist[i.se] = dist[cur] + i.fi;
pq.emplace(dist[i.se], i.se);
}
}
}
cout << dist[d] << '\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... |