#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5;
int n, m, s, t, u, v;
vector<pair<int, int>> adj[N];
int du[N], dv[N], ds[N], dt[N];
void dijkstra(int src, int dist[]) {
fill(dist, dist + N, 1e18);
dist[src] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(greater<>())> pq;
bool done[N] = {};
pq.push({0, src});
while (!pq.empty()) {
int temp = pq.top().second;
pq.pop();
if (done[temp])
continue;
done[temp] = true;
for (auto i : adj[temp]) {
if (dist[i.first] > dist[temp] + i.second) {
dist[i.first] = dist[temp] + i.second;
pq.push({dist[i.first], i.first});
}
}
}
}
int solve() {
dijkstra(u, du);
dijkstra(v, dv);
dijkstra(t, dt);
int mv[N];
fill(mv, mv + N, 1e18);
mv[s] = du[s];
fill(ds, ds + N, 1e18);
ds[s] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(greater<>())> pq;
bool done[N] = {};
pq.push({0, s});
int ans = du[v];
while (!pq.empty()) {
int temp = pq.top().second;
pq.pop();
if (done[temp])
continue;
done[temp] = true;
mv[temp] = min(mv[temp], du[temp]);
if (ds[temp] + dt[temp] == dt[s])
ans = min(ans, mv[temp] + dv[temp]);
for (auto i : adj[temp]) {
if (ds[i.first] > ds[temp] + i.second) {
ds[i.first] = ds[temp] + i.second;
pq.push({ds[i.first], i.first});
mv[i.first] = mv[temp];
} else if (ds[i.first] == ds[temp] + i.second) {
mv[i.first] = min(mv[i.first], mv[temp]);
}
}
}
return ans;
}
void solveTestCase() {
cin >> n >> m >> s >> t >> u >> v;
s--, t--, u--, v--;
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
a--, b--;
adj[a].emplace_back(b, c);
adj[b].emplace_back(a, c);
}
int ans = solve();
swap(u, v);
cout << min(ans, solve());
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int test = 1;
// cin >> test;
while (test--)
solveTestCase();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
502 ms |
24212 KB |
Output is correct |
2 |
Correct |
517 ms |
22752 KB |
Output is correct |
3 |
Correct |
485 ms |
23972 KB |
Output is correct |
4 |
Correct |
512 ms |
24152 KB |
Output is correct |
5 |
Correct |
565 ms |
22416 KB |
Output is correct |
6 |
Correct |
545 ms |
24308 KB |
Output is correct |
7 |
Correct |
518 ms |
22600 KB |
Output is correct |
8 |
Correct |
493 ms |
22692 KB |
Output is correct |
9 |
Correct |
487 ms |
23408 KB |
Output is correct |
10 |
Correct |
390 ms |
23372 KB |
Output is correct |
11 |
Correct |
170 ms |
14072 KB |
Output is correct |
12 |
Correct |
527 ms |
23168 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
525 ms |
22928 KB |
Output is correct |
2 |
Correct |
617 ms |
22676 KB |
Output is correct |
3 |
Correct |
523 ms |
22644 KB |
Output is correct |
4 |
Correct |
520 ms |
22672 KB |
Output is correct |
5 |
Correct |
522 ms |
22648 KB |
Output is correct |
6 |
Correct |
573 ms |
22964 KB |
Output is correct |
7 |
Correct |
518 ms |
22532 KB |
Output is correct |
8 |
Correct |
544 ms |
22660 KB |
Output is correct |
9 |
Correct |
520 ms |
22652 KB |
Output is correct |
10 |
Correct |
516 ms |
22636 KB |
Output is correct |
11 |
Correct |
157 ms |
14200 KB |
Output is correct |
12 |
Correct |
524 ms |
23016 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
8576 KB |
Output is correct |
2 |
Correct |
8 ms |
6912 KB |
Output is correct |
3 |
Correct |
9 ms |
6912 KB |
Output is correct |
4 |
Correct |
25 ms |
10240 KB |
Output is correct |
5 |
Correct |
16 ms |
8576 KB |
Output is correct |
6 |
Correct |
9 ms |
6784 KB |
Output is correct |
7 |
Correct |
9 ms |
7040 KB |
Output is correct |
8 |
Correct |
11 ms |
7168 KB |
Output is correct |
9 |
Correct |
9 ms |
6912 KB |
Output is correct |
10 |
Correct |
18 ms |
8576 KB |
Output is correct |
11 |
Correct |
8 ms |
6912 KB |
Output is correct |
12 |
Correct |
10 ms |
6784 KB |
Output is correct |
13 |
Correct |
9 ms |
6784 KB |
Output is correct |
14 |
Correct |
10 ms |
6912 KB |
Output is correct |
15 |
Correct |
9 ms |
6912 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
502 ms |
24212 KB |
Output is correct |
2 |
Correct |
517 ms |
22752 KB |
Output is correct |
3 |
Correct |
485 ms |
23972 KB |
Output is correct |
4 |
Correct |
512 ms |
24152 KB |
Output is correct |
5 |
Correct |
565 ms |
22416 KB |
Output is correct |
6 |
Correct |
545 ms |
24308 KB |
Output is correct |
7 |
Correct |
518 ms |
22600 KB |
Output is correct |
8 |
Correct |
493 ms |
22692 KB |
Output is correct |
9 |
Correct |
487 ms |
23408 KB |
Output is correct |
10 |
Correct |
390 ms |
23372 KB |
Output is correct |
11 |
Correct |
170 ms |
14072 KB |
Output is correct |
12 |
Correct |
527 ms |
23168 KB |
Output is correct |
13 |
Correct |
525 ms |
22928 KB |
Output is correct |
14 |
Correct |
617 ms |
22676 KB |
Output is correct |
15 |
Correct |
523 ms |
22644 KB |
Output is correct |
16 |
Correct |
520 ms |
22672 KB |
Output is correct |
17 |
Correct |
522 ms |
22648 KB |
Output is correct |
18 |
Correct |
573 ms |
22964 KB |
Output is correct |
19 |
Correct |
518 ms |
22532 KB |
Output is correct |
20 |
Correct |
544 ms |
22660 KB |
Output is correct |
21 |
Correct |
520 ms |
22652 KB |
Output is correct |
22 |
Correct |
516 ms |
22636 KB |
Output is correct |
23 |
Correct |
157 ms |
14200 KB |
Output is correct |
24 |
Correct |
524 ms |
23016 KB |
Output is correct |
25 |
Correct |
17 ms |
8576 KB |
Output is correct |
26 |
Correct |
8 ms |
6912 KB |
Output is correct |
27 |
Correct |
9 ms |
6912 KB |
Output is correct |
28 |
Correct |
25 ms |
10240 KB |
Output is correct |
29 |
Correct |
16 ms |
8576 KB |
Output is correct |
30 |
Correct |
9 ms |
6784 KB |
Output is correct |
31 |
Correct |
9 ms |
7040 KB |
Output is correct |
32 |
Correct |
11 ms |
7168 KB |
Output is correct |
33 |
Correct |
9 ms |
6912 KB |
Output is correct |
34 |
Correct |
18 ms |
8576 KB |
Output is correct |
35 |
Correct |
8 ms |
6912 KB |
Output is correct |
36 |
Correct |
10 ms |
6784 KB |
Output is correct |
37 |
Correct |
9 ms |
6784 KB |
Output is correct |
38 |
Correct |
10 ms |
6912 KB |
Output is correct |
39 |
Correct |
9 ms |
6912 KB |
Output is correct |
40 |
Correct |
564 ms |
24192 KB |
Output is correct |
41 |
Correct |
478 ms |
23360 KB |
Output is correct |
42 |
Correct |
497 ms |
23408 KB |
Output is correct |
43 |
Correct |
163 ms |
14200 KB |
Output is correct |
44 |
Correct |
171 ms |
14200 KB |
Output is correct |
45 |
Correct |
420 ms |
22308 KB |
Output is correct |
46 |
Correct |
406 ms |
21932 KB |
Output is correct |
47 |
Correct |
488 ms |
24092 KB |
Output is correct |
48 |
Correct |
186 ms |
13560 KB |
Output is correct |
49 |
Correct |
391 ms |
23808 KB |
Output is correct |
50 |
Correct |
439 ms |
22380 KB |
Output is correct |
51 |
Correct |
403 ms |
22200 KB |
Output is correct |