#include <iostream>
#include <vector>
using namespace std;
#define rep(i, a, b) for (auto i = (a); i < (b); ++i)
#define trav(x, v) for (auto &x : v)
#define eb(x...) emplace_back(x)
#define ff first
#define ss second
using ll = int64_t;
using vl = vector<ll>;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
template<class T> bool ckmin(T& a, const T& b) { return a > b ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
const int N = 1 << 17;
const ll inf = 1e18;
vector<pii> g[N];
#include <ext/pb_ds/priority_queue.hpp>
using namespace __gnu_pbds;
using pq = __gnu_pbds::priority_queue<pli, greater<pli>, thin_heap_tag>;
int n;
vl dij(int s) {
vl dist(n, inf); dist[s] = 0; pq q;
vector<pq::point_iterator> it(n);
rep(i, 0, n) it[i] = q.push({dist[i], i});
while (!q.empty()) {
int u = q.top().ss; q.pop();
trav(e, g[u])
if (ckmin(dist[e.ff], dist[u] + e.ss))
q.modify(it[e.ff], {dist[e.ff], e.ff});
}
return dist;
}
ll mx[N], my[N];
vl ds, dx, dy;
pll dfs(int u) {
if (mx[u] == inf) {
mx[u] = dx[u]; my[u] = dy[u];
trav(e, g[u]) {
if (ds[u] < ds[e.ff] + e.ss) continue;
auto dv = dfs(e.ff);
if (dx[u] + dv.ss < mx[u] + my[u])
mx[u] = dx[u], my[u] = dv.ss;
if (dv.ff + dy[u] < mx[u] + my[u])
mx[u] = dv.ff, my[u] = dy[u];
if (dv.ff + dv.ss < mx[u] + my[u])
mx[u] = dv.ff, my[u] = dv.ss;
}
}
return {mx[u], my[u]};
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int m, s, t, x, y; cin >> n >> m >> s >> t >> x >> y; --s; --t; --x; --y;
while (m--) {
int u, v, w; cin >> u >> v >> w; --u; --v;
g[u].eb(v, w); g[v].eb(u, w);
}
ds = dij(s); dx = dij(x); dy = dij(y);
rep(u, 0, n) mx[u] = my[u] = inf;
cout << min(dx[y], dfs(t).ff + dfs(t).ss);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
603 ms |
18872 KB |
Output is correct |
2 |
Correct |
536 ms |
18872 KB |
Output is correct |
3 |
Correct |
539 ms |
18844 KB |
Output is correct |
4 |
Correct |
578 ms |
18860 KB |
Output is correct |
5 |
Correct |
519 ms |
18848 KB |
Output is correct |
6 |
Correct |
613 ms |
18844 KB |
Output is correct |
7 |
Correct |
510 ms |
18860 KB |
Output is correct |
8 |
Correct |
507 ms |
22312 KB |
Output is correct |
9 |
Correct |
618 ms |
23124 KB |
Output is correct |
10 |
Correct |
536 ms |
23268 KB |
Output is correct |
11 |
Correct |
361 ms |
18024 KB |
Output is correct |
12 |
Correct |
637 ms |
23076 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
578 ms |
18888 KB |
Output is correct |
2 |
Correct |
552 ms |
22364 KB |
Output is correct |
3 |
Correct |
548 ms |
22356 KB |
Output is correct |
4 |
Correct |
545 ms |
22352 KB |
Output is correct |
5 |
Correct |
550 ms |
22364 KB |
Output is correct |
6 |
Correct |
528 ms |
22664 KB |
Output is correct |
7 |
Correct |
551 ms |
22308 KB |
Output is correct |
8 |
Correct |
546 ms |
22248 KB |
Output is correct |
9 |
Correct |
525 ms |
22356 KB |
Output is correct |
10 |
Correct |
581 ms |
22476 KB |
Output is correct |
11 |
Correct |
354 ms |
18024 KB |
Output is correct |
12 |
Correct |
539 ms |
22576 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
4088 KB |
Output is correct |
2 |
Correct |
7 ms |
3448 KB |
Output is correct |
3 |
Correct |
8 ms |
3448 KB |
Output is correct |
4 |
Correct |
22 ms |
4736 KB |
Output is correct |
5 |
Correct |
14 ms |
4088 KB |
Output is correct |
6 |
Correct |
9 ms |
3448 KB |
Output is correct |
7 |
Correct |
8 ms |
3448 KB |
Output is correct |
8 |
Correct |
8 ms |
3580 KB |
Output is correct |
9 |
Correct |
8 ms |
3448 KB |
Output is correct |
10 |
Correct |
14 ms |
4088 KB |
Output is correct |
11 |
Correct |
7 ms |
3448 KB |
Output is correct |
12 |
Correct |
7 ms |
3448 KB |
Output is correct |
13 |
Correct |
7 ms |
3448 KB |
Output is correct |
14 |
Correct |
7 ms |
3448 KB |
Output is correct |
15 |
Correct |
7 ms |
3448 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
603 ms |
18872 KB |
Output is correct |
2 |
Correct |
536 ms |
18872 KB |
Output is correct |
3 |
Correct |
539 ms |
18844 KB |
Output is correct |
4 |
Correct |
578 ms |
18860 KB |
Output is correct |
5 |
Correct |
519 ms |
18848 KB |
Output is correct |
6 |
Correct |
613 ms |
18844 KB |
Output is correct |
7 |
Correct |
510 ms |
18860 KB |
Output is correct |
8 |
Correct |
507 ms |
22312 KB |
Output is correct |
9 |
Correct |
618 ms |
23124 KB |
Output is correct |
10 |
Correct |
536 ms |
23268 KB |
Output is correct |
11 |
Correct |
361 ms |
18024 KB |
Output is correct |
12 |
Correct |
637 ms |
23076 KB |
Output is correct |
13 |
Correct |
578 ms |
18888 KB |
Output is correct |
14 |
Correct |
552 ms |
22364 KB |
Output is correct |
15 |
Correct |
548 ms |
22356 KB |
Output is correct |
16 |
Correct |
545 ms |
22352 KB |
Output is correct |
17 |
Correct |
550 ms |
22364 KB |
Output is correct |
18 |
Correct |
528 ms |
22664 KB |
Output is correct |
19 |
Correct |
551 ms |
22308 KB |
Output is correct |
20 |
Correct |
546 ms |
22248 KB |
Output is correct |
21 |
Correct |
525 ms |
22356 KB |
Output is correct |
22 |
Correct |
581 ms |
22476 KB |
Output is correct |
23 |
Correct |
354 ms |
18024 KB |
Output is correct |
24 |
Correct |
539 ms |
22576 KB |
Output is correct |
25 |
Correct |
15 ms |
4088 KB |
Output is correct |
26 |
Correct |
7 ms |
3448 KB |
Output is correct |
27 |
Correct |
8 ms |
3448 KB |
Output is correct |
28 |
Correct |
22 ms |
4736 KB |
Output is correct |
29 |
Correct |
14 ms |
4088 KB |
Output is correct |
30 |
Correct |
9 ms |
3448 KB |
Output is correct |
31 |
Correct |
8 ms |
3448 KB |
Output is correct |
32 |
Correct |
8 ms |
3580 KB |
Output is correct |
33 |
Correct |
8 ms |
3448 KB |
Output is correct |
34 |
Correct |
14 ms |
4088 KB |
Output is correct |
35 |
Correct |
7 ms |
3448 KB |
Output is correct |
36 |
Correct |
7 ms |
3448 KB |
Output is correct |
37 |
Correct |
7 ms |
3448 KB |
Output is correct |
38 |
Correct |
7 ms |
3448 KB |
Output is correct |
39 |
Correct |
7 ms |
3448 KB |
Output is correct |
40 |
Correct |
543 ms |
22788 KB |
Output is correct |
41 |
Correct |
613 ms |
23080 KB |
Output is correct |
42 |
Correct |
632 ms |
23124 KB |
Output is correct |
43 |
Correct |
380 ms |
18024 KB |
Output is correct |
44 |
Correct |
373 ms |
18024 KB |
Output is correct |
45 |
Correct |
545 ms |
22316 KB |
Output is correct |
46 |
Correct |
529 ms |
22044 KB |
Output is correct |
47 |
Correct |
599 ms |
22684 KB |
Output is correct |
48 |
Correct |
360 ms |
17500 KB |
Output is correct |
49 |
Correct |
502 ms |
22392 KB |
Output is correct |
50 |
Correct |
540 ms |
22232 KB |
Output is correct |
51 |
Correct |
532 ms |
22312 KB |
Output is correct |