#include <bits/stdc++.h>
#define inf 1'000'000'000'000'000
#define int long long
using namespace std;
typedef pair<int, int> ii;
vector<ii> graf[100005];
int du[100005];
int dv[100005];
int ds[100005];
int dp[5][100005];
int rez = 0;
bool ob[100005];
void dijkstra1(int start, int arr[])
{
memset(ob, false, sizeof(ob));
priority_queue<ii, vector<ii>, greater<ii>> pq;
pq.push({0, start});
while (!pq.empty())
{
auto [d, u] = pq.top();
pq.pop();
if (ob[u])
continue;
arr[u] = d;
ob[u] = 1;
for (auto [v, w] : graf[u])
pq.push({d + w, v});
}
}
void dijkstra2(int start, int end)
{
memset(dp, -1, sizeof(dp));
memset(ob, false, sizeof(ob));
priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;
pq.push({0, start, 0});
dp[0][0] = dp[1][0] = inf;
while (!pq.empty())
{
auto [d, u, par] = pq.top();
pq.pop();
if (!ob[u])
{
ob[u] = 1;
ds[u] = d;
dp[0][u] = min(du[u], dp[0][par]);
dp[1][u] = min(dv[u], dp[1][par]);
for (auto [v, w] : graf[u])
pq.push({d + w, v, u});
}
else if (d == ds[u])
{
if (min(du[u], dp[0][par]) + min(dv[u], dp[1][par]) <= dp[0][u] + dp[1][u])
{
dp[0][u] = min(du[u], dp[0][par]);
dp[1][u] = min(dv[u], dp[1][par]);
}
}
}
rez = min(rez, dp[0][end] + dp[1][end]);
}
int32_t main()
{
int n, m, s, t, u, v;
cin >> n >> m >> s >> t >> u >> v;
for (int i = 0; i < m; i++)
{
int a, b, c;
cin >> a >> b >> c;
graf[a].push_back({b, c});
graf[b].push_back({a, c});
}
dijkstra1(u, du);
dijkstra1(v, dv);
rez = du[v];
dijkstra2(s, t);
dijkstra2(t, s);
cout << rez << '\n';
return 0;
}
Compilation message
commuter_pass.cpp: In function 'void dijkstra1(long long int, long long int*)':
commuter_pass.cpp:25:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
25 | auto [d, u] = pq.top();
| ^
commuter_pass.cpp:31:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
31 | for (auto [v, w] : graf[u])
| ^
commuter_pass.cpp: In function 'void dijkstra2(long long int, long long int)':
commuter_pass.cpp:45:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
45 | auto [d, u, par] = pq.top();
| ^
commuter_pass.cpp:53:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
53 | for (auto [v, w] : graf[u])
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
521 ms |
31656 KB |
Output is correct |
2 |
Correct |
456 ms |
30448 KB |
Output is correct |
3 |
Correct |
464 ms |
32488 KB |
Output is correct |
4 |
Correct |
520 ms |
34112 KB |
Output is correct |
5 |
Correct |
457 ms |
28804 KB |
Output is correct |
6 |
Correct |
493 ms |
34732 KB |
Output is correct |
7 |
Correct |
436 ms |
33204 KB |
Output is correct |
8 |
Correct |
433 ms |
33868 KB |
Output is correct |
9 |
Correct |
527 ms |
35072 KB |
Output is correct |
10 |
Correct |
505 ms |
35388 KB |
Output is correct |
11 |
Correct |
138 ms |
16360 KB |
Output is correct |
12 |
Correct |
480 ms |
34716 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
477 ms |
30684 KB |
Output is correct |
2 |
Correct |
433 ms |
25336 KB |
Output is correct |
3 |
Correct |
479 ms |
30580 KB |
Output is correct |
4 |
Correct |
429 ms |
25552 KB |
Output is correct |
5 |
Correct |
425 ms |
25308 KB |
Output is correct |
6 |
Correct |
455 ms |
30656 KB |
Output is correct |
7 |
Correct |
421 ms |
25456 KB |
Output is correct |
8 |
Correct |
449 ms |
25588 KB |
Output is correct |
9 |
Correct |
458 ms |
25672 KB |
Output is correct |
10 |
Correct |
425 ms |
30596 KB |
Output is correct |
11 |
Correct |
128 ms |
14116 KB |
Output is correct |
12 |
Correct |
466 ms |
29756 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
37 ms |
11752 KB |
Output is correct |
2 |
Correct |
3 ms |
9052 KB |
Output is correct |
3 |
Correct |
2 ms |
9048 KB |
Output is correct |
4 |
Correct |
76 ms |
15240 KB |
Output is correct |
5 |
Correct |
38 ms |
13132 KB |
Output is correct |
6 |
Correct |
4 ms |
9316 KB |
Output is correct |
7 |
Correct |
6 ms |
9392 KB |
Output is correct |
8 |
Correct |
7 ms |
9564 KB |
Output is correct |
9 |
Correct |
4 ms |
9308 KB |
Output is correct |
10 |
Correct |
37 ms |
13048 KB |
Output is correct |
11 |
Correct |
2 ms |
9052 KB |
Output is correct |
12 |
Correct |
2 ms |
9052 KB |
Output is correct |
13 |
Correct |
3 ms |
9052 KB |
Output is correct |
14 |
Correct |
4 ms |
9052 KB |
Output is correct |
15 |
Correct |
3 ms |
9048 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
521 ms |
31656 KB |
Output is correct |
2 |
Correct |
456 ms |
30448 KB |
Output is correct |
3 |
Correct |
464 ms |
32488 KB |
Output is correct |
4 |
Correct |
520 ms |
34112 KB |
Output is correct |
5 |
Correct |
457 ms |
28804 KB |
Output is correct |
6 |
Correct |
493 ms |
34732 KB |
Output is correct |
7 |
Correct |
436 ms |
33204 KB |
Output is correct |
8 |
Correct |
433 ms |
33868 KB |
Output is correct |
9 |
Correct |
527 ms |
35072 KB |
Output is correct |
10 |
Correct |
505 ms |
35388 KB |
Output is correct |
11 |
Correct |
138 ms |
16360 KB |
Output is correct |
12 |
Correct |
480 ms |
34716 KB |
Output is correct |
13 |
Correct |
477 ms |
30684 KB |
Output is correct |
14 |
Correct |
433 ms |
25336 KB |
Output is correct |
15 |
Correct |
479 ms |
30580 KB |
Output is correct |
16 |
Correct |
429 ms |
25552 KB |
Output is correct |
17 |
Correct |
425 ms |
25308 KB |
Output is correct |
18 |
Correct |
455 ms |
30656 KB |
Output is correct |
19 |
Correct |
421 ms |
25456 KB |
Output is correct |
20 |
Correct |
449 ms |
25588 KB |
Output is correct |
21 |
Correct |
458 ms |
25672 KB |
Output is correct |
22 |
Correct |
425 ms |
30596 KB |
Output is correct |
23 |
Correct |
128 ms |
14116 KB |
Output is correct |
24 |
Correct |
466 ms |
29756 KB |
Output is correct |
25 |
Correct |
37 ms |
11752 KB |
Output is correct |
26 |
Correct |
3 ms |
9052 KB |
Output is correct |
27 |
Correct |
2 ms |
9048 KB |
Output is correct |
28 |
Correct |
76 ms |
15240 KB |
Output is correct |
29 |
Correct |
38 ms |
13132 KB |
Output is correct |
30 |
Correct |
4 ms |
9316 KB |
Output is correct |
31 |
Correct |
6 ms |
9392 KB |
Output is correct |
32 |
Correct |
7 ms |
9564 KB |
Output is correct |
33 |
Correct |
4 ms |
9308 KB |
Output is correct |
34 |
Correct |
37 ms |
13048 KB |
Output is correct |
35 |
Correct |
2 ms |
9052 KB |
Output is correct |
36 |
Correct |
2 ms |
9052 KB |
Output is correct |
37 |
Correct |
3 ms |
9052 KB |
Output is correct |
38 |
Correct |
4 ms |
9052 KB |
Output is correct |
39 |
Correct |
3 ms |
9048 KB |
Output is correct |
40 |
Correct |
476 ms |
34824 KB |
Output is correct |
41 |
Correct |
497 ms |
34912 KB |
Output is correct |
42 |
Correct |
536 ms |
35288 KB |
Output is correct |
43 |
Correct |
146 ms |
16460 KB |
Output is correct |
44 |
Correct |
131 ms |
16332 KB |
Output is correct |
45 |
Correct |
477 ms |
27580 KB |
Output is correct |
46 |
Correct |
432 ms |
27220 KB |
Output is correct |
47 |
Correct |
488 ms |
29388 KB |
Output is correct |
48 |
Correct |
134 ms |
15880 KB |
Output is correct |
49 |
Correct |
483 ms |
33492 KB |
Output is correct |
50 |
Correct |
433 ms |
29152 KB |
Output is correct |
51 |
Correct |
434 ms |
29044 KB |
Output is correct |