이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define ft first
#define sc second
#define ll long long
#define all(x) x.begin(),x.end()
#define bit(x, i) ((x >> i)&1)
#define pii pair<int, int>
using namespace std;
const int N = 1e5 + 2;
vector<pii> ad[N];
#define plli pair<ll,int>
long long f[6][N];
int tt[N], n, m, TR[6][N];
const ll INF = (ll)1e18 + 7;
void dijkstra(int s) {
int d = tt[s];
priority_queue<plli, vector<plli>, less<plli> > pq;
for (int i = 1; i <= n; i++) {
f[d][i] = INF;
}
f[d][s] = 0;
pq.push({f[d][s], s});
while (pq.size()) {
long long value = pq.top().ft;
int numb = pq.top().sc;
pq.pop();
if (value != f[d][numb]) continue;
for (pii u : ad[numb]) {
if (value + 1ll * u.sc < f[d][u.ft]) {
f[d][u.ft] = value + 1ll * u.sc;
TR[d][u.ft] = numb;
pq.push({f[d][u.ft], u.ft});
}
}
}
}
int s, t, u, v;
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
// freopen("in.inp", "r", stdin);
cin >> n >> m;
cin >> s >> t >> u >> v;
tt[s] = 1; tt[t] = 2; tt[u] = 3; tt[v] = 4;
int a, b, c;
for (int i = 1; i <= m; i++) {
cin >> a >> b >> c;
ad[a].push_back({b, c});
ad[b].push_back({a, c});
}
dijkstra(s);
dijkstra(u);
dijkstra(v);
vector<int> check(n + 1, 0);
int p = t;
check[s] = check[t] = 1;
long long resu = INF, resv = INF;
while (p != s) {
check[p] = 1;
resu = min(resu, f[tt[u]][p]);
resv = min(resv, f[tt[v]][p]);
p = TR[tt[s]][p];
}
resu = min(resu, f[tt[u]][s]);
resv = min(resv, f[tt[v]][s]);
if (u == v) cout << 0;
else {
cout << min(f[tt[u]][v], resu + resv);
}
}
# | 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... |