#include "bits/stdc++.h"
using namespace std;
#define s second
#define f first
#define pb push_back
typedef long long ll;
typedef pair<ll, ll> pii;
const ll INF = 1e17 + 10ll;
int main() {
ll n, m;
cin >> n >> m;
ll s, t;
cin >> s >> t;
ll u, v;
cin >> u >> v;
u--;v--;s--;t--;
vector<vector<pii> > adj(n);
for (ll i = 0; i < m; i++) {
ll a,b,w;
cin >> a >> b >> w;
adj[--a].push_back({--b, w});
adj[b].push_back({a, w});
}
vector<ll> distu(n, -1);
vector<ll> distv(n, -1);
// distu[u]=0;
// distv[v]=0;
priority_queue<pii> q;
q.push({0, u});
while (!q.empty()) {
ll cur = q.top().s;
ll dist = q.top().f;
q.pop();
if (distu[cur] >= 0ll) continue;
distu[cur] = -dist;
// cout << cur << endl;
for (auto val: adj[cur]) {
if (distu[val.f] == -1ll) {
q.push({-distu[cur] - val.s, val.f});
}
}
}
q.push({0, v});
while (!q.empty()) {
ll cur = q.top().s;
ll dist = q.top().f;
q.pop();
if (distv[cur] >= 0ll) continue;
distv[cur] = -dist;
// cout << cur << endl;
for (auto val: adj[cur]) {
if (distv[val.f] == -1ll) {
q.push({-distv[cur] - val.s, val.f});
}
}
}
vector<ll> minans(n, INF);
vector<ll> minprev(n, INF);
vector<ll> minans1(n, INF);
vector<ll> minprev1(n, INF);
vector<ll> dist(n, -1);
priority_queue<pair<ll, pii> > bq;
for (auto val: adj[s]) bq.push({-val.s, {val.f, s}});
dist[s]=0;
minprev[s] = distu[s];
minans[s] = distu[v];
minprev1[s] = distv[s];
minans1[s] = distv[u];
assert(distu[v]==distv[u]);
while (!bq.empty()) {
ll cur = bq.top().s.f;
ll prev = bq.top().s.s;
ll d = bq.top().f;
bq.pop();
if (-d > dist[cur] && dist[cur]!=-1) continue;
bool prevdone = (dist[cur] != -1);
assert(dist[cur] == -1 || dist[cur]==-d);
dist[cur] = -d;
minprev[cur] = min(min(minprev[prev], distu[cur]), minprev[cur]);
minans[cur] = min(min(minans[prev], minprev[cur] + distv[cur]), minans[cur]);
minprev1[cur] = min(min(minprev1[prev], distv[cur]), minprev1[cur]);
minans1[cur] = min(min(minans1[prev], minprev1[cur] + distu[cur]), minans1[cur]);
// cout << cur << minprev[cur] << endl;
if (prevdone) continue;
for (auto val: adj[cur]) {
if (dist[val.f] == -1) {
bq.push({-dist[cur] - val.s, {val.f, cur}});
}
}
}
cout << min(minans[t], minans1[t]) << endl;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
428 ms |
24796 KB |
Output is correct |
2 |
Correct |
386 ms |
24540 KB |
Output is correct |
3 |
Correct |
461 ms |
24208 KB |
Output is correct |
4 |
Correct |
423 ms |
24640 KB |
Output is correct |
5 |
Correct |
453 ms |
24228 KB |
Output is correct |
6 |
Correct |
422 ms |
24832 KB |
Output is correct |
7 |
Correct |
401 ms |
24364 KB |
Output is correct |
8 |
Correct |
426 ms |
24376 KB |
Output is correct |
9 |
Correct |
465 ms |
24460 KB |
Output is correct |
10 |
Correct |
425 ms |
29048 KB |
Output is correct |
11 |
Correct |
165 ms |
15368 KB |
Output is correct |
12 |
Correct |
433 ms |
28732 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
441 ms |
24640 KB |
Output is correct |
2 |
Correct |
376 ms |
22756 KB |
Output is correct |
3 |
Correct |
376 ms |
22740 KB |
Output is correct |
4 |
Correct |
427 ms |
22888 KB |
Output is correct |
5 |
Correct |
358 ms |
22764 KB |
Output is correct |
6 |
Correct |
387 ms |
24188 KB |
Output is correct |
7 |
Correct |
377 ms |
22828 KB |
Output is correct |
8 |
Correct |
365 ms |
22672 KB |
Output is correct |
9 |
Correct |
385 ms |
22772 KB |
Output is correct |
10 |
Correct |
404 ms |
22820 KB |
Output is correct |
11 |
Correct |
157 ms |
13260 KB |
Output is correct |
12 |
Correct |
376 ms |
24272 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
27 ms |
2340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
54 ms |
5252 KB |
Output is correct |
5 |
Correct |
28 ms |
3380 KB |
Output is correct |
6 |
Correct |
3 ms |
468 KB |
Output is correct |
7 |
Correct |
3 ms |
596 KB |
Output is correct |
8 |
Correct |
5 ms |
664 KB |
Output is correct |
9 |
Correct |
3 ms |
448 KB |
Output is correct |
10 |
Correct |
29 ms |
3020 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
2 ms |
340 KB |
Output is correct |
14 |
Correct |
3 ms |
308 KB |
Output is correct |
15 |
Correct |
2 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
428 ms |
24796 KB |
Output is correct |
2 |
Correct |
386 ms |
24540 KB |
Output is correct |
3 |
Correct |
461 ms |
24208 KB |
Output is correct |
4 |
Correct |
423 ms |
24640 KB |
Output is correct |
5 |
Correct |
453 ms |
24228 KB |
Output is correct |
6 |
Correct |
422 ms |
24832 KB |
Output is correct |
7 |
Correct |
401 ms |
24364 KB |
Output is correct |
8 |
Correct |
426 ms |
24376 KB |
Output is correct |
9 |
Correct |
465 ms |
24460 KB |
Output is correct |
10 |
Correct |
425 ms |
29048 KB |
Output is correct |
11 |
Correct |
165 ms |
15368 KB |
Output is correct |
12 |
Correct |
433 ms |
28732 KB |
Output is correct |
13 |
Correct |
441 ms |
24640 KB |
Output is correct |
14 |
Correct |
376 ms |
22756 KB |
Output is correct |
15 |
Correct |
376 ms |
22740 KB |
Output is correct |
16 |
Correct |
427 ms |
22888 KB |
Output is correct |
17 |
Correct |
358 ms |
22764 KB |
Output is correct |
18 |
Correct |
387 ms |
24188 KB |
Output is correct |
19 |
Correct |
377 ms |
22828 KB |
Output is correct |
20 |
Correct |
365 ms |
22672 KB |
Output is correct |
21 |
Correct |
385 ms |
22772 KB |
Output is correct |
22 |
Correct |
404 ms |
22820 KB |
Output is correct |
23 |
Correct |
157 ms |
13260 KB |
Output is correct |
24 |
Correct |
376 ms |
24272 KB |
Output is correct |
25 |
Correct |
27 ms |
2340 KB |
Output is correct |
26 |
Correct |
1 ms |
340 KB |
Output is correct |
27 |
Correct |
1 ms |
340 KB |
Output is correct |
28 |
Correct |
54 ms |
5252 KB |
Output is correct |
29 |
Correct |
28 ms |
3380 KB |
Output is correct |
30 |
Correct |
3 ms |
468 KB |
Output is correct |
31 |
Correct |
3 ms |
596 KB |
Output is correct |
32 |
Correct |
5 ms |
664 KB |
Output is correct |
33 |
Correct |
3 ms |
448 KB |
Output is correct |
34 |
Correct |
29 ms |
3020 KB |
Output is correct |
35 |
Correct |
1 ms |
340 KB |
Output is correct |
36 |
Correct |
1 ms |
340 KB |
Output is correct |
37 |
Correct |
2 ms |
340 KB |
Output is correct |
38 |
Correct |
3 ms |
308 KB |
Output is correct |
39 |
Correct |
2 ms |
340 KB |
Output is correct |
40 |
Correct |
415 ms |
28296 KB |
Output is correct |
41 |
Correct |
435 ms |
28668 KB |
Output is correct |
42 |
Correct |
417 ms |
28728 KB |
Output is correct |
43 |
Correct |
181 ms |
15432 KB |
Output is correct |
44 |
Correct |
159 ms |
15452 KB |
Output is correct |
45 |
Correct |
402 ms |
24988 KB |
Output is correct |
46 |
Correct |
391 ms |
24700 KB |
Output is correct |
47 |
Correct |
419 ms |
28220 KB |
Output is correct |
48 |
Correct |
157 ms |
14904 KB |
Output is correct |
49 |
Correct |
407 ms |
27684 KB |
Output is correct |
50 |
Correct |
411 ms |
25104 KB |
Output is correct |
51 |
Correct |
348 ms |
24920 KB |
Output is correct |