#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 100100;
vector<pair<int, int>> g[N];
void dkstr(int u, vector<ll> &d) {
set<pair<ll, int>> s;
fill(d.begin(), d.end(), 1e15);
d[u] = 0;
s.insert({0, u});
while(!s.empty()) {
int v = s.begin() -> second;
ll f = s.begin() -> first;
s.erase(s.begin());
if(d[v] != f) continue;
for(auto to : g[v]) {
if(d[to.first] > d[v] + to.second) {
d[to.first] = d[v] + to.second;
s.insert({d[to.first], to.first});
}
}
}
}
int main() {
int n, m, s, t, u, v; cin >> n >> m;
cin >> s >> t >> u >> v;
for(int i = 1; i <= m; i++) {
int x, y, w; cin >> x >> y >> w;
g[x].emplace_back(y, w);
g[y].emplace_back(x, w);
}
vector<ll> fs(n + 1), ft(n + 1), fu(n + 1), fv(n + 1);
dkstr(s, fs);
dkstr(t, ft);
dkstr(u, fu);
dkstr(v, fv);
ll ans = fu[v];
for(int it = 0; it < 2; it++) {
vector<ll> mn(n + 1, 1e15), f(n + 1, 1e15);
set<pair<ll, int>> d;
d.insert({0, s});
f[s] = 0;
mn[s] = fu[s];
while(!d.empty()) {
int x = d.begin() -> second;
ll y = d.begin() -> first;
d.erase(d.begin());
if(f[x] != y) continue;
ans = min(ans, mn[x] + fv[x]);
for(auto to : g[x]) {
if(fs[to.first] + ft[to.first] == fs[t]) {
mn[to.first] = min(mn[to.first], min(mn[x], fu[to.first]));
if(f[to.first] > to.second + y) {
f[to.first] = to.second + y;
d.insert({f[to.first], to.first});
}
}
}
}
swap(fu, fv);
}
cout << ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
690 ms |
20164 KB |
Output is correct |
2 |
Correct |
654 ms |
19836 KB |
Output is correct |
3 |
Correct |
691 ms |
19764 KB |
Output is correct |
4 |
Correct |
685 ms |
20064 KB |
Output is correct |
5 |
Correct |
613 ms |
18500 KB |
Output is correct |
6 |
Correct |
772 ms |
20412 KB |
Output is correct |
7 |
Correct |
665 ms |
19024 KB |
Output is correct |
8 |
Correct |
659 ms |
19284 KB |
Output is correct |
9 |
Correct |
627 ms |
20036 KB |
Output is correct |
10 |
Correct |
531 ms |
20396 KB |
Output is correct |
11 |
Correct |
237 ms |
12484 KB |
Output is correct |
12 |
Correct |
613 ms |
20036 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
733 ms |
19568 KB |
Output is correct |
2 |
Correct |
674 ms |
19544 KB |
Output is correct |
3 |
Correct |
644 ms |
18776 KB |
Output is correct |
4 |
Correct |
773 ms |
18784 KB |
Output is correct |
5 |
Correct |
661 ms |
18800 KB |
Output is correct |
6 |
Correct |
659 ms |
20164 KB |
Output is correct |
7 |
Correct |
744 ms |
18728 KB |
Output is correct |
8 |
Correct |
680 ms |
18780 KB |
Output is correct |
9 |
Correct |
662 ms |
19496 KB |
Output is correct |
10 |
Correct |
656 ms |
19396 KB |
Output is correct |
11 |
Correct |
242 ms |
12484 KB |
Output is correct |
12 |
Correct |
671 ms |
19668 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
3652 KB |
Output is correct |
2 |
Correct |
3 ms |
2636 KB |
Output is correct |
3 |
Correct |
3 ms |
2636 KB |
Output is correct |
4 |
Correct |
45 ms |
4732 KB |
Output is correct |
5 |
Correct |
24 ms |
3592 KB |
Output is correct |
6 |
Correct |
4 ms |
2636 KB |
Output is correct |
7 |
Correct |
6 ms |
2764 KB |
Output is correct |
8 |
Correct |
6 ms |
2764 KB |
Output is correct |
9 |
Correct |
4 ms |
2636 KB |
Output is correct |
10 |
Correct |
23 ms |
3680 KB |
Output is correct |
11 |
Correct |
2 ms |
2636 KB |
Output is correct |
12 |
Correct |
2 ms |
2636 KB |
Output is correct |
13 |
Correct |
3 ms |
2636 KB |
Output is correct |
14 |
Correct |
3 ms |
2636 KB |
Output is correct |
15 |
Correct |
3 ms |
2636 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
690 ms |
20164 KB |
Output is correct |
2 |
Correct |
654 ms |
19836 KB |
Output is correct |
3 |
Correct |
691 ms |
19764 KB |
Output is correct |
4 |
Correct |
685 ms |
20064 KB |
Output is correct |
5 |
Correct |
613 ms |
18500 KB |
Output is correct |
6 |
Correct |
772 ms |
20412 KB |
Output is correct |
7 |
Correct |
665 ms |
19024 KB |
Output is correct |
8 |
Correct |
659 ms |
19284 KB |
Output is correct |
9 |
Correct |
627 ms |
20036 KB |
Output is correct |
10 |
Correct |
531 ms |
20396 KB |
Output is correct |
11 |
Correct |
237 ms |
12484 KB |
Output is correct |
12 |
Correct |
613 ms |
20036 KB |
Output is correct |
13 |
Correct |
733 ms |
19568 KB |
Output is correct |
14 |
Correct |
674 ms |
19544 KB |
Output is correct |
15 |
Correct |
644 ms |
18776 KB |
Output is correct |
16 |
Correct |
773 ms |
18784 KB |
Output is correct |
17 |
Correct |
661 ms |
18800 KB |
Output is correct |
18 |
Correct |
659 ms |
20164 KB |
Output is correct |
19 |
Correct |
744 ms |
18728 KB |
Output is correct |
20 |
Correct |
680 ms |
18780 KB |
Output is correct |
21 |
Correct |
662 ms |
19496 KB |
Output is correct |
22 |
Correct |
656 ms |
19396 KB |
Output is correct |
23 |
Correct |
242 ms |
12484 KB |
Output is correct |
24 |
Correct |
671 ms |
19668 KB |
Output is correct |
25 |
Correct |
24 ms |
3652 KB |
Output is correct |
26 |
Correct |
3 ms |
2636 KB |
Output is correct |
27 |
Correct |
3 ms |
2636 KB |
Output is correct |
28 |
Correct |
45 ms |
4732 KB |
Output is correct |
29 |
Correct |
24 ms |
3592 KB |
Output is correct |
30 |
Correct |
4 ms |
2636 KB |
Output is correct |
31 |
Correct |
6 ms |
2764 KB |
Output is correct |
32 |
Correct |
6 ms |
2764 KB |
Output is correct |
33 |
Correct |
4 ms |
2636 KB |
Output is correct |
34 |
Correct |
23 ms |
3680 KB |
Output is correct |
35 |
Correct |
2 ms |
2636 KB |
Output is correct |
36 |
Correct |
2 ms |
2636 KB |
Output is correct |
37 |
Correct |
3 ms |
2636 KB |
Output is correct |
38 |
Correct |
3 ms |
2636 KB |
Output is correct |
39 |
Correct |
3 ms |
2636 KB |
Output is correct |
40 |
Correct |
775 ms |
22100 KB |
Output is correct |
41 |
Correct |
677 ms |
20560 KB |
Output is correct |
42 |
Correct |
667 ms |
19584 KB |
Output is correct |
43 |
Correct |
271 ms |
12568 KB |
Output is correct |
44 |
Correct |
283 ms |
12584 KB |
Output is correct |
45 |
Correct |
645 ms |
18888 KB |
Output is correct |
46 |
Correct |
613 ms |
18760 KB |
Output is correct |
47 |
Correct |
733 ms |
19848 KB |
Output is correct |
48 |
Correct |
269 ms |
12100 KB |
Output is correct |
49 |
Correct |
563 ms |
21656 KB |
Output is correct |
50 |
Correct |
632 ms |
18208 KB |
Output is correct |
51 |
Correct |
638 ms |
19012 KB |
Output is correct |