#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) {
fill(d.begin(), d.end(), 1e15);
d[u] = 0;
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> s;
s.push({0, u});
while(s.size()) {
int v = s.top().second;
ll f = s.top().first;
s.pop();
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.push({d[to.first], to.first});
}
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
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);
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> d;
d.push({0, s});
f[s] = 0;
mn[s] = fu[s];
while(d.size()) {
int x = d.top().second;
ll y = d.top().first;
d.pop();
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.push({f[to.first], to.first});
}
}
}
}
swap(fu, fv);
}
cout << ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
336 ms |
15208 KB |
Output is correct |
2 |
Correct |
378 ms |
14028 KB |
Output is correct |
3 |
Correct |
413 ms |
15056 KB |
Output is correct |
4 |
Correct |
338 ms |
15024 KB |
Output is correct |
5 |
Correct |
388 ms |
14028 KB |
Output is correct |
6 |
Correct |
365 ms |
15248 KB |
Output is correct |
7 |
Correct |
410 ms |
13944 KB |
Output is correct |
8 |
Correct |
380 ms |
14092 KB |
Output is correct |
9 |
Correct |
349 ms |
13852 KB |
Output is correct |
10 |
Correct |
288 ms |
13672 KB |
Output is correct |
11 |
Correct |
171 ms |
10504 KB |
Output is correct |
12 |
Correct |
354 ms |
13804 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
414 ms |
14108 KB |
Output is correct |
2 |
Correct |
397 ms |
13920 KB |
Output is correct |
3 |
Correct |
389 ms |
13960 KB |
Output is correct |
4 |
Correct |
389 ms |
14000 KB |
Output is correct |
5 |
Correct |
404 ms |
14124 KB |
Output is correct |
6 |
Correct |
387 ms |
14356 KB |
Output is correct |
7 |
Correct |
465 ms |
14632 KB |
Output is correct |
8 |
Correct |
363 ms |
13956 KB |
Output is correct |
9 |
Correct |
375 ms |
14012 KB |
Output is correct |
10 |
Correct |
375 ms |
13948 KB |
Output is correct |
11 |
Correct |
147 ms |
10404 KB |
Output is correct |
12 |
Correct |
412 ms |
14420 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
3404 KB |
Output is correct |
2 |
Correct |
3 ms |
2636 KB |
Output is correct |
3 |
Correct |
2 ms |
2636 KB |
Output is correct |
4 |
Correct |
18 ms |
4032 KB |
Output is correct |
5 |
Correct |
12 ms |
3276 KB |
Output is correct |
6 |
Correct |
3 ms |
2636 KB |
Output is correct |
7 |
Correct |
4 ms |
2764 KB |
Output is correct |
8 |
Correct |
4 ms |
2764 KB |
Output is correct |
9 |
Correct |
3 ms |
2764 KB |
Output is correct |
10 |
Correct |
10 ms |
3276 KB |
Output is correct |
11 |
Correct |
2 ms |
2636 KB |
Output is correct |
12 |
Correct |
2 ms |
2636 KB |
Output is correct |
13 |
Correct |
2 ms |
2636 KB |
Output is correct |
14 |
Correct |
2 ms |
2636 KB |
Output is correct |
15 |
Correct |
2 ms |
2636 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
336 ms |
15208 KB |
Output is correct |
2 |
Correct |
378 ms |
14028 KB |
Output is correct |
3 |
Correct |
413 ms |
15056 KB |
Output is correct |
4 |
Correct |
338 ms |
15024 KB |
Output is correct |
5 |
Correct |
388 ms |
14028 KB |
Output is correct |
6 |
Correct |
365 ms |
15248 KB |
Output is correct |
7 |
Correct |
410 ms |
13944 KB |
Output is correct |
8 |
Correct |
380 ms |
14092 KB |
Output is correct |
9 |
Correct |
349 ms |
13852 KB |
Output is correct |
10 |
Correct |
288 ms |
13672 KB |
Output is correct |
11 |
Correct |
171 ms |
10504 KB |
Output is correct |
12 |
Correct |
354 ms |
13804 KB |
Output is correct |
13 |
Correct |
414 ms |
14108 KB |
Output is correct |
14 |
Correct |
397 ms |
13920 KB |
Output is correct |
15 |
Correct |
389 ms |
13960 KB |
Output is correct |
16 |
Correct |
389 ms |
14000 KB |
Output is correct |
17 |
Correct |
404 ms |
14124 KB |
Output is correct |
18 |
Correct |
387 ms |
14356 KB |
Output is correct |
19 |
Correct |
465 ms |
14632 KB |
Output is correct |
20 |
Correct |
363 ms |
13956 KB |
Output is correct |
21 |
Correct |
375 ms |
14012 KB |
Output is correct |
22 |
Correct |
375 ms |
13948 KB |
Output is correct |
23 |
Correct |
147 ms |
10404 KB |
Output is correct |
24 |
Correct |
412 ms |
14420 KB |
Output is correct |
25 |
Correct |
10 ms |
3404 KB |
Output is correct |
26 |
Correct |
3 ms |
2636 KB |
Output is correct |
27 |
Correct |
2 ms |
2636 KB |
Output is correct |
28 |
Correct |
18 ms |
4032 KB |
Output is correct |
29 |
Correct |
12 ms |
3276 KB |
Output is correct |
30 |
Correct |
3 ms |
2636 KB |
Output is correct |
31 |
Correct |
4 ms |
2764 KB |
Output is correct |
32 |
Correct |
4 ms |
2764 KB |
Output is correct |
33 |
Correct |
3 ms |
2764 KB |
Output is correct |
34 |
Correct |
10 ms |
3276 KB |
Output is correct |
35 |
Correct |
2 ms |
2636 KB |
Output is correct |
36 |
Correct |
2 ms |
2636 KB |
Output is correct |
37 |
Correct |
2 ms |
2636 KB |
Output is correct |
38 |
Correct |
2 ms |
2636 KB |
Output is correct |
39 |
Correct |
2 ms |
2636 KB |
Output is correct |
40 |
Correct |
322 ms |
15320 KB |
Output is correct |
41 |
Correct |
325 ms |
13932 KB |
Output is correct |
42 |
Correct |
360 ms |
13944 KB |
Output is correct |
43 |
Correct |
213 ms |
10480 KB |
Output is correct |
44 |
Correct |
239 ms |
10464 KB |
Output is correct |
45 |
Correct |
375 ms |
15148 KB |
Output is correct |
46 |
Correct |
419 ms |
15084 KB |
Output is correct |
47 |
Correct |
322 ms |
15092 KB |
Output is correct |
48 |
Correct |
207 ms |
10480 KB |
Output is correct |
49 |
Correct |
273 ms |
15224 KB |
Output is correct |
50 |
Correct |
391 ms |
14516 KB |
Output is correct |
51 |
Correct |
387 ms |
15184 KB |
Output is correct |