#include <algorithm>
#include <iostream>
#include <vector>
#include <limits>
#include <queue>
#include <random>
#include <time.h>
using namespace std;
typedef long long ll;
ll N, M, S, T, U, V, dist[5][100005];
vector<pair<ll, ll>> routes[100005];
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
void dk(ll s, ll id) {
fill(begin(dist[id]), end(dist[id]), numeric_limits<ll>::max());
dist[id][s] = 0;
pq.push({ 0, s });
while (!pq.empty()) {
auto curr = pq.top();
pq.pop();
if (curr.first > dist[id][curr.second]) continue;
for (auto child : routes[curr.second]) {
if (child.first + curr.first < dist[id][child.second]) {
dist[id][child.second] = child.first + curr.first;
pq.push({ dist[id][child.second], child.second });
}
}
}
}
ll solve(ll first, ll second) {
fill(begin(dist[3]), end(dist[3]), numeric_limits<ll>::max());
ll output = dist[first][S] + dist[second][S];
dist[3][S] = dist[first][S];
pq.push({ dist[3][S], S });
while (!pq.empty()) {
auto curr = pq.top();
pq.pop();
if (curr.first > dist[3][curr.second]) continue;
for (auto child : routes[curr.second]) {
if (dist[0][child.second] + child.first == dist[0][curr.second]) {
ll newD = min(dist[first][child.second], dist[3][curr.second]);
if (newD < dist[3][child.second]) {
output = min(output, newD + dist[second][child.second]);
dist[3][child.second] = newD;
pq.push({ newD, child.second });
}
}
}
}
return output;
}
ll genRand() {
return rand() % N + 1;
}
int main() {
srand(time(NULL));
cin.tie(0); ios::sync_with_stdio(0);
cin >> N >> M >> S >> T >> U >> V;
if (T == U || T == V) swap(S, T);
for (ll i = 0, a, b, c; i < M; ++i) {
cin >> a >> b >> c;
routes[a].push_back({ c, b });
routes[b].push_back({ c, a });
}
for (ll rep = 0; rep < 1; ++rep) {
//S = genRand(), T = genRand(), U = genRand(), V = genRand();
dk(T, 0); // dist[0] = nuke path
dk(U, 1); // dist[1] = distances to U
dk(V, 2); // dist[2] = distances to V
// dist[3] = u_x to u + v_x to v (1 then 2 or 2 then 1)
//cout << S << T << " " << U << V << " ";
cout << min({ solve(1, 2), solve(2, 1), dist[1][V] }) << "\n";
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
292 ms |
17372 KB |
Output is correct |
2 |
Correct |
311 ms |
17248 KB |
Output is correct |
3 |
Correct |
361 ms |
17372 KB |
Output is correct |
4 |
Correct |
289 ms |
17636 KB |
Output is correct |
5 |
Correct |
332 ms |
17120 KB |
Output is correct |
6 |
Correct |
327 ms |
17508 KB |
Output is correct |
7 |
Correct |
350 ms |
17320 KB |
Output is correct |
8 |
Correct |
353 ms |
17376 KB |
Output is correct |
9 |
Correct |
336 ms |
17120 KB |
Output is correct |
10 |
Correct |
254 ms |
16992 KB |
Output is correct |
11 |
Correct |
146 ms |
11116 KB |
Output is correct |
12 |
Correct |
317 ms |
17120 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
320 ms |
17376 KB |
Output is correct |
2 |
Correct |
335 ms |
17252 KB |
Output is correct |
3 |
Correct |
341 ms |
17252 KB |
Output is correct |
4 |
Correct |
331 ms |
17384 KB |
Output is correct |
5 |
Correct |
362 ms |
17380 KB |
Output is correct |
6 |
Correct |
344 ms |
17548 KB |
Output is correct |
7 |
Correct |
390 ms |
17896 KB |
Output is correct |
8 |
Correct |
341 ms |
17636 KB |
Output is correct |
9 |
Correct |
352 ms |
17888 KB |
Output is correct |
10 |
Correct |
331 ms |
17724 KB |
Output is correct |
11 |
Correct |
153 ms |
11628 KB |
Output is correct |
12 |
Correct |
364 ms |
20084 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
7148 KB |
Output is correct |
2 |
Correct |
4 ms |
5868 KB |
Output is correct |
3 |
Correct |
4 ms |
5868 KB |
Output is correct |
4 |
Correct |
19 ms |
8556 KB |
Output is correct |
5 |
Correct |
12 ms |
7148 KB |
Output is correct |
6 |
Correct |
5 ms |
5868 KB |
Output is correct |
7 |
Correct |
5 ms |
5996 KB |
Output is correct |
8 |
Correct |
6 ms |
5996 KB |
Output is correct |
9 |
Correct |
6 ms |
5868 KB |
Output is correct |
10 |
Correct |
11 ms |
7148 KB |
Output is correct |
11 |
Correct |
4 ms |
5868 KB |
Output is correct |
12 |
Correct |
4 ms |
5888 KB |
Output is correct |
13 |
Correct |
4 ms |
5868 KB |
Output is correct |
14 |
Correct |
4 ms |
5868 KB |
Output is correct |
15 |
Correct |
4 ms |
5868 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
292 ms |
17372 KB |
Output is correct |
2 |
Correct |
311 ms |
17248 KB |
Output is correct |
3 |
Correct |
361 ms |
17372 KB |
Output is correct |
4 |
Correct |
289 ms |
17636 KB |
Output is correct |
5 |
Correct |
332 ms |
17120 KB |
Output is correct |
6 |
Correct |
327 ms |
17508 KB |
Output is correct |
7 |
Correct |
350 ms |
17320 KB |
Output is correct |
8 |
Correct |
353 ms |
17376 KB |
Output is correct |
9 |
Correct |
336 ms |
17120 KB |
Output is correct |
10 |
Correct |
254 ms |
16992 KB |
Output is correct |
11 |
Correct |
146 ms |
11116 KB |
Output is correct |
12 |
Correct |
317 ms |
17120 KB |
Output is correct |
13 |
Correct |
320 ms |
17376 KB |
Output is correct |
14 |
Correct |
335 ms |
17252 KB |
Output is correct |
15 |
Correct |
341 ms |
17252 KB |
Output is correct |
16 |
Correct |
331 ms |
17384 KB |
Output is correct |
17 |
Correct |
362 ms |
17380 KB |
Output is correct |
18 |
Correct |
344 ms |
17548 KB |
Output is correct |
19 |
Correct |
390 ms |
17896 KB |
Output is correct |
20 |
Correct |
341 ms |
17636 KB |
Output is correct |
21 |
Correct |
352 ms |
17888 KB |
Output is correct |
22 |
Correct |
331 ms |
17724 KB |
Output is correct |
23 |
Correct |
153 ms |
11628 KB |
Output is correct |
24 |
Correct |
364 ms |
20084 KB |
Output is correct |
25 |
Correct |
18 ms |
7148 KB |
Output is correct |
26 |
Correct |
4 ms |
5868 KB |
Output is correct |
27 |
Correct |
4 ms |
5868 KB |
Output is correct |
28 |
Correct |
19 ms |
8556 KB |
Output is correct |
29 |
Correct |
12 ms |
7148 KB |
Output is correct |
30 |
Correct |
5 ms |
5868 KB |
Output is correct |
31 |
Correct |
5 ms |
5996 KB |
Output is correct |
32 |
Correct |
6 ms |
5996 KB |
Output is correct |
33 |
Correct |
6 ms |
5868 KB |
Output is correct |
34 |
Correct |
11 ms |
7148 KB |
Output is correct |
35 |
Correct |
4 ms |
5868 KB |
Output is correct |
36 |
Correct |
4 ms |
5888 KB |
Output is correct |
37 |
Correct |
4 ms |
5868 KB |
Output is correct |
38 |
Correct |
4 ms |
5868 KB |
Output is correct |
39 |
Correct |
4 ms |
5868 KB |
Output is correct |
40 |
Correct |
311 ms |
18180 KB |
Output is correct |
41 |
Correct |
302 ms |
18408 KB |
Output is correct |
42 |
Correct |
299 ms |
18532 KB |
Output is correct |
43 |
Correct |
190 ms |
12268 KB |
Output is correct |
44 |
Correct |
190 ms |
12396 KB |
Output is correct |
45 |
Correct |
425 ms |
18272 KB |
Output is correct |
46 |
Correct |
439 ms |
18020 KB |
Output is correct |
47 |
Correct |
341 ms |
18580 KB |
Output is correct |
48 |
Correct |
192 ms |
12396 KB |
Output is correct |
49 |
Correct |
260 ms |
18212 KB |
Output is correct |
50 |
Correct |
727 ms |
18144 KB |
Output is correct |
51 |
Correct |
370 ms |
18016 KB |
Output is correct |