#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ar array
const int mxN = 100000;
int n, m, s1, t1, s2, t2, id[mxN];
vector<pair<int, int>> adj[mxN];
ll d1[mxN], d2[mxN], d3[mxN], d4[mxN], pre[mxN], suf[mxN];
bool vis[mxN];
void dijk(int s, ll d[]) {
memset(vis, 0, n);
memset(d, 0x3f, 8 * n);
d[s] = 0;
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
pq.emplace(0, s);
while(!pq.empty()) {
int u = pq.top().second; pq.pop();
if (vis[u])
continue;
vis[u] = 1;
for (pair<int, int> v : adj[u])
if (d[u] + v.second < d[v.first])
pq.emplace(d[v.first] = d[u] + v.second, v.first);
}
}
void solve(ll dp[], ll d[], ll du[]) {
sort(id, id + n, [&](int a, int b) {return d[a] < d[b];});
for (int i = 0; i < n; ++i) {
dp[id[i]] = du[id[i]];
for (pair<int, int> j : adj[id[i]])
if (d[j.first] + j.second == d[id[i]])
dp[id[i]] = min(dp[id[i]], dp[j.first]);
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> s1 >> t1 >> s2 >> t2, --s1, --t1, --s2, --t2;
for (int i = 0, u, v, w; i < m; ++i) {
cin >> u >> v >> w, --u, --v;
adj[u].emplace_back(v, w);
adj[v].emplace_back(u, w);
}
dijk(s1, d1);
dijk(t1, d2);
dijk(s2, d3);
dijk(t2, d4);
iota(id, id + n, 0);
ll spath = d1[t1];
ll ans = d3[t2];
for (int rep = 0; rep < 2; ++rep) {
solve(pre, d1, d3);
solve(suf, d2, d4);
//for (int i = 0; i < n; ++i)
// cout << pre[i] << " " << suf[i] << "\n";
for (int i = 0; i < n; ++i)
if (d1[i] + d2[i] == spath)
ans = min(ans, pre[i] + suf[i]);
for (int i = 0; i < n; ++i)
swap(d3[i], d4[i]);
}
cout << ans;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
437 ms |
16476 KB |
Output is correct |
2 |
Correct |
420 ms |
17832 KB |
Output is correct |
3 |
Correct |
479 ms |
19560 KB |
Output is correct |
4 |
Correct |
409 ms |
19204 KB |
Output is correct |
5 |
Correct |
404 ms |
17676 KB |
Output is correct |
6 |
Correct |
432 ms |
19264 KB |
Output is correct |
7 |
Correct |
412 ms |
17788 KB |
Output is correct |
8 |
Correct |
400 ms |
17692 KB |
Output is correct |
9 |
Correct |
402 ms |
18800 KB |
Output is correct |
10 |
Correct |
376 ms |
18764 KB |
Output is correct |
11 |
Correct |
197 ms |
13036 KB |
Output is correct |
12 |
Correct |
466 ms |
18684 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
415 ms |
15196 KB |
Output is correct |
2 |
Correct |
447 ms |
15048 KB |
Output is correct |
3 |
Correct |
408 ms |
15316 KB |
Output is correct |
4 |
Correct |
406 ms |
15076 KB |
Output is correct |
5 |
Correct |
405 ms |
14968 KB |
Output is correct |
6 |
Correct |
462 ms |
15032 KB |
Output is correct |
7 |
Correct |
399 ms |
15112 KB |
Output is correct |
8 |
Correct |
445 ms |
15216 KB |
Output is correct |
9 |
Correct |
409 ms |
14968 KB |
Output is correct |
10 |
Correct |
409 ms |
15020 KB |
Output is correct |
11 |
Correct |
174 ms |
11884 KB |
Output is correct |
12 |
Correct |
424 ms |
15036 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
3820 KB |
Output is correct |
2 |
Correct |
3 ms |
2796 KB |
Output is correct |
3 |
Correct |
3 ms |
2796 KB |
Output is correct |
4 |
Correct |
19 ms |
4844 KB |
Output is correct |
5 |
Correct |
10 ms |
3820 KB |
Output is correct |
6 |
Correct |
3 ms |
2796 KB |
Output is correct |
7 |
Correct |
4 ms |
2924 KB |
Output is correct |
8 |
Correct |
5 ms |
2944 KB |
Output is correct |
9 |
Correct |
3 ms |
2796 KB |
Output is correct |
10 |
Correct |
10 ms |
3820 KB |
Output is correct |
11 |
Correct |
2 ms |
2796 KB |
Output is correct |
12 |
Correct |
2 ms |
2796 KB |
Output is correct |
13 |
Correct |
2 ms |
2796 KB |
Output is correct |
14 |
Correct |
4 ms |
2796 KB |
Output is correct |
15 |
Correct |
3 ms |
2796 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
437 ms |
16476 KB |
Output is correct |
2 |
Correct |
420 ms |
17832 KB |
Output is correct |
3 |
Correct |
479 ms |
19560 KB |
Output is correct |
4 |
Correct |
409 ms |
19204 KB |
Output is correct |
5 |
Correct |
404 ms |
17676 KB |
Output is correct |
6 |
Correct |
432 ms |
19264 KB |
Output is correct |
7 |
Correct |
412 ms |
17788 KB |
Output is correct |
8 |
Correct |
400 ms |
17692 KB |
Output is correct |
9 |
Correct |
402 ms |
18800 KB |
Output is correct |
10 |
Correct |
376 ms |
18764 KB |
Output is correct |
11 |
Correct |
197 ms |
13036 KB |
Output is correct |
12 |
Correct |
466 ms |
18684 KB |
Output is correct |
13 |
Correct |
415 ms |
15196 KB |
Output is correct |
14 |
Correct |
447 ms |
15048 KB |
Output is correct |
15 |
Correct |
408 ms |
15316 KB |
Output is correct |
16 |
Correct |
406 ms |
15076 KB |
Output is correct |
17 |
Correct |
405 ms |
14968 KB |
Output is correct |
18 |
Correct |
462 ms |
15032 KB |
Output is correct |
19 |
Correct |
399 ms |
15112 KB |
Output is correct |
20 |
Correct |
445 ms |
15216 KB |
Output is correct |
21 |
Correct |
409 ms |
14968 KB |
Output is correct |
22 |
Correct |
409 ms |
15020 KB |
Output is correct |
23 |
Correct |
174 ms |
11884 KB |
Output is correct |
24 |
Correct |
424 ms |
15036 KB |
Output is correct |
25 |
Correct |
11 ms |
3820 KB |
Output is correct |
26 |
Correct |
3 ms |
2796 KB |
Output is correct |
27 |
Correct |
3 ms |
2796 KB |
Output is correct |
28 |
Correct |
19 ms |
4844 KB |
Output is correct |
29 |
Correct |
10 ms |
3820 KB |
Output is correct |
30 |
Correct |
3 ms |
2796 KB |
Output is correct |
31 |
Correct |
4 ms |
2924 KB |
Output is correct |
32 |
Correct |
5 ms |
2944 KB |
Output is correct |
33 |
Correct |
3 ms |
2796 KB |
Output is correct |
34 |
Correct |
10 ms |
3820 KB |
Output is correct |
35 |
Correct |
2 ms |
2796 KB |
Output is correct |
36 |
Correct |
2 ms |
2796 KB |
Output is correct |
37 |
Correct |
2 ms |
2796 KB |
Output is correct |
38 |
Correct |
4 ms |
2796 KB |
Output is correct |
39 |
Correct |
3 ms |
2796 KB |
Output is correct |
40 |
Correct |
404 ms |
19584 KB |
Output is correct |
41 |
Correct |
414 ms |
18460 KB |
Output is correct |
42 |
Correct |
406 ms |
18736 KB |
Output is correct |
43 |
Correct |
172 ms |
13164 KB |
Output is correct |
44 |
Correct |
214 ms |
13164 KB |
Output is correct |
45 |
Correct |
380 ms |
18476 KB |
Output is correct |
46 |
Correct |
362 ms |
17652 KB |
Output is correct |
47 |
Correct |
466 ms |
19088 KB |
Output is correct |
48 |
Correct |
164 ms |
12524 KB |
Output is correct |
49 |
Correct |
397 ms |
19196 KB |
Output is correct |
50 |
Correct |
457 ms |
17780 KB |
Output is correct |
51 |
Correct |
470 ms |
17684 KB |
Output is correct |