#define USE_MATH_DEFINES 1
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define MOD 998244353ll
#define INF 1000000000000000000ll
#define EPS 1e-9
#define getchar_unlocked _getchar_nolock
#define putchar_unlocked _putchar_nolock
typedef long long ll;
typedef long double ld;
typedef pair <ll,ll> pl;
typedef tuple <ll,ll,ll> tl;
ll N, M, S, T, U, V, D1[100005], D2[100005], C[100005][4];
vector <pl> adj[100005];
std::priority_queue <tl, vector<tl>, greater<tl> > pq;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> N >> M >> S >> T >> U >> V;
for (ll i = 1; i <= M; i++) {
ll a, b, c;
cin >> a >> b >> c;
adj[a].emplace_back(c, b);
adj[b].emplace_back(c, a);
}
for (ll i = 1; i <= N; i++) {
D1[i] = INF;
D2[i] = INF;
C[i][0] = INF;
C[i][1] = INF;
C[i][2] = INF;
C[i][3] = INF;
}
D1[S] = 0;
pq.emplace(0, S, -1);
while (!pq.empty()) {
ll curnode = get<1>(pq.top());
ll curdist = get<0>(pq.top());
pq.pop();
if (curdist > D1[curnode]) continue;
for (pl edge : adj[curnode]) {
ll nexnode = edge.second;
ll nexdist = D1[curnode] + edge.first;
if (nexdist < D1[nexnode]) {
D1[nexnode] = nexdist;
pq.emplace(D1[nexnode], nexnode, -1);
}
}
}
D2[T] = 0;
pq.emplace(0, T, -1);
while (!pq.empty()) {
ll curnode = get<1>(pq.top());
ll curdist = get<0>(pq.top());
pq.pop();
if (curdist > D2[curnode]) continue;
for (pl edge : adj[curnode]) {
ll nexnode = edge.second;
ll nexdist = D2[curnode] + edge.first;
if (nexdist < D2[nexnode]) {
D2[nexnode] = nexdist;
pq.emplace(D2[nexnode], nexnode, -1);
}
}
}
C[U][0] = 0;
pq.emplace(0, U, 0);
while (!pq.empty()) {
ll curnode = get<1>(pq.top());
ll curdist = get<0>(pq.top());
ll state = get<2>(pq.top());
pq.pop();
if (curdist > C[curnode][state]) continue;
for (pl edge : adj[curnode]) {
ll nexnode = edge.second;
ll edgewgt = edge.first;
// 0 -> 0
if (state == 0 && C[curnode][0] + edgewgt < C[nexnode][0]) {
C[nexnode][0] = C[curnode][0] + edgewgt;
pq.emplace(C[nexnode][0], nexnode, 0);
}
// 0 or 1 -> 1
if ((state == 0 || state == 1) && C[curnode][state] < C[nexnode][1]
&& D1[curnode] + edgewgt + D2[nexnode] == D1[T]) {
C[nexnode][1] = C[curnode][state];
pq.emplace(C[nexnode][1], nexnode, 1);
}
// 0 or 2 -> 2
if ((state == 0 || state == 2) && C[curnode][state] < C[nexnode][2]
&& D2[curnode] + edgewgt + D1[nexnode] == D1[T]) {
C[nexnode][2] = C[curnode][state];
pq.emplace(C[nexnode][2], nexnode, 2);
}
// 1 or 2 or 3 -> 3
if (state != 0 && C[curnode][state] + edgewgt < C[nexnode][3]) {
C[nexnode][3] = C[curnode][state] + edgewgt;
pq.emplace(C[nexnode][3], nexnode, 3);
}
}
}
cout << min(min(min(C[V][0], C[V][1]), C[V][2]), C[V][3]);
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
358 ms |
27876 KB |
Output is correct |
2 |
Correct |
428 ms |
24556 KB |
Output is correct |
3 |
Correct |
445 ms |
27744 KB |
Output is correct |
4 |
Correct |
389 ms |
24936 KB |
Output is correct |
5 |
Correct |
432 ms |
27488 KB |
Output is correct |
6 |
Correct |
382 ms |
28000 KB |
Output is correct |
7 |
Correct |
457 ms |
27616 KB |
Output is correct |
8 |
Correct |
432 ms |
27516 KB |
Output is correct |
9 |
Correct |
411 ms |
25452 KB |
Output is correct |
10 |
Correct |
310 ms |
25576 KB |
Output is correct |
11 |
Correct |
182 ms |
16372 KB |
Output is correct |
12 |
Correct |
421 ms |
25192 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
475 ms |
24808 KB |
Output is correct |
2 |
Correct |
475 ms |
24552 KB |
Output is correct |
3 |
Correct |
472 ms |
27496 KB |
Output is correct |
4 |
Correct |
437 ms |
24424 KB |
Output is correct |
5 |
Correct |
433 ms |
24424 KB |
Output is correct |
6 |
Correct |
432 ms |
27908 KB |
Output is correct |
7 |
Correct |
466 ms |
27496 KB |
Output is correct |
8 |
Correct |
461 ms |
24540 KB |
Output is correct |
9 |
Correct |
456 ms |
24424 KB |
Output is correct |
10 |
Correct |
464 ms |
24424 KB |
Output is correct |
11 |
Correct |
201 ms |
17904 KB |
Output is correct |
12 |
Correct |
442 ms |
27748 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
4608 KB |
Output is correct |
2 |
Correct |
6 ms |
2816 KB |
Output is correct |
3 |
Correct |
6 ms |
2816 KB |
Output is correct |
4 |
Correct |
24 ms |
6144 KB |
Output is correct |
5 |
Correct |
15 ms |
4528 KB |
Output is correct |
6 |
Correct |
7 ms |
2944 KB |
Output is correct |
7 |
Correct |
8 ms |
3072 KB |
Output is correct |
8 |
Correct |
8 ms |
2944 KB |
Output is correct |
9 |
Correct |
7 ms |
2816 KB |
Output is correct |
10 |
Correct |
15 ms |
4480 KB |
Output is correct |
11 |
Correct |
7 ms |
2720 KB |
Output is correct |
12 |
Correct |
6 ms |
2688 KB |
Output is correct |
13 |
Correct |
7 ms |
2816 KB |
Output is correct |
14 |
Correct |
6 ms |
2816 KB |
Output is correct |
15 |
Correct |
7 ms |
2816 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
358 ms |
27876 KB |
Output is correct |
2 |
Correct |
428 ms |
24556 KB |
Output is correct |
3 |
Correct |
445 ms |
27744 KB |
Output is correct |
4 |
Correct |
389 ms |
24936 KB |
Output is correct |
5 |
Correct |
432 ms |
27488 KB |
Output is correct |
6 |
Correct |
382 ms |
28000 KB |
Output is correct |
7 |
Correct |
457 ms |
27616 KB |
Output is correct |
8 |
Correct |
432 ms |
27516 KB |
Output is correct |
9 |
Correct |
411 ms |
25452 KB |
Output is correct |
10 |
Correct |
310 ms |
25576 KB |
Output is correct |
11 |
Correct |
182 ms |
16372 KB |
Output is correct |
12 |
Correct |
421 ms |
25192 KB |
Output is correct |
13 |
Correct |
475 ms |
24808 KB |
Output is correct |
14 |
Correct |
475 ms |
24552 KB |
Output is correct |
15 |
Correct |
472 ms |
27496 KB |
Output is correct |
16 |
Correct |
437 ms |
24424 KB |
Output is correct |
17 |
Correct |
433 ms |
24424 KB |
Output is correct |
18 |
Correct |
432 ms |
27908 KB |
Output is correct |
19 |
Correct |
466 ms |
27496 KB |
Output is correct |
20 |
Correct |
461 ms |
24540 KB |
Output is correct |
21 |
Correct |
456 ms |
24424 KB |
Output is correct |
22 |
Correct |
464 ms |
24424 KB |
Output is correct |
23 |
Correct |
201 ms |
17904 KB |
Output is correct |
24 |
Correct |
442 ms |
27748 KB |
Output is correct |
25 |
Correct |
15 ms |
4608 KB |
Output is correct |
26 |
Correct |
6 ms |
2816 KB |
Output is correct |
27 |
Correct |
6 ms |
2816 KB |
Output is correct |
28 |
Correct |
24 ms |
6144 KB |
Output is correct |
29 |
Correct |
15 ms |
4528 KB |
Output is correct |
30 |
Correct |
7 ms |
2944 KB |
Output is correct |
31 |
Correct |
8 ms |
3072 KB |
Output is correct |
32 |
Correct |
8 ms |
2944 KB |
Output is correct |
33 |
Correct |
7 ms |
2816 KB |
Output is correct |
34 |
Correct |
15 ms |
4480 KB |
Output is correct |
35 |
Correct |
7 ms |
2720 KB |
Output is correct |
36 |
Correct |
6 ms |
2688 KB |
Output is correct |
37 |
Correct |
7 ms |
2816 KB |
Output is correct |
38 |
Correct |
6 ms |
2816 KB |
Output is correct |
39 |
Correct |
7 ms |
2816 KB |
Output is correct |
40 |
Correct |
385 ms |
28516 KB |
Output is correct |
41 |
Correct |
361 ms |
23408 KB |
Output is correct |
42 |
Correct |
389 ms |
23536 KB |
Output is correct |
43 |
Correct |
233 ms |
18028 KB |
Output is correct |
44 |
Correct |
232 ms |
18028 KB |
Output is correct |
45 |
Correct |
448 ms |
27628 KB |
Output is correct |
46 |
Correct |
436 ms |
27236 KB |
Output is correct |
47 |
Correct |
375 ms |
24808 KB |
Output is correct |
48 |
Correct |
246 ms |
17392 KB |
Output is correct |
49 |
Correct |
311 ms |
28380 KB |
Output is correct |
50 |
Correct |
455 ms |
27624 KB |
Output is correct |
51 |
Correct |
451 ms |
27492 KB |
Output is correct |