#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;
const int maxn = 100005;
const long long inf = (1LL << 62);
vector<pair<long long, long long>> g[maxn];
long long du[maxn];
long long dv[maxn];
long long ds[maxn];
long long dp[2][maxn];
long long ans = 0;
bool visited[maxn];
void dijkstra1(long long start_node, long long dist[])
{
fill(dist, dist + maxn, inf);
priority_queue<pair<long long, long long>> pq;
pq.push({0, start_node});
dist[start_node] = 0;
while (!pq.empty())
{
long long curr = -pq.top().first;
long long node = pq.top().second;
pq.pop();
if (dist[node] < curr) continue;
for (auto [v, w] : g[node])
{
long long path = curr + w;
if (dist[v] > path)
{
dist[v] = path;
pq.push({-path, v});
}
}
}
}
void dijkstra2(long long beg_node, long long end_node)
{
fill(dp[0], dp[0] + maxn, inf);
fill(dp[1], dp[1] + maxn, inf);
fill(visited, visited + maxn, 0);
priority_queue<pair<long long, pair<long long, long long>>> pq;
pq.push({0, {beg_node, 0}});
dp[0][0] = dp[1][0] = inf;
while (!pq.empty())
{
long long curr = -pq.top().first;
long long node = pq.top().second.first;
long long par = pq.top().second.second;
pq.pop();
if (!visited[node])
{
visited[node] = true;
ds[node] = curr;
dp[0][node] = min(du[node], dp[0][par]);
dp[1][node] = min(dv[node], dp[1][par]);
for (auto [v, w] : g[node])
{
if (!visited[v])
{
pq.push({-curr - w, {v, node}});
}
}
} else if (curr == ds[node])
{
if (min(du[node], dp[0][par]) + min(dv[node], dp[1][par]) <= dp[0][node] + dp[1][node])
{
dp[0][node] = min(du[node], dp[0][par]);
dp[1][node] = min(dv[node], dp[1][par]);
}
}
}
ans = min(ans, dp[0][end_node] + dp[1][end_node]);
}
void fastIO()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
int main()
{
fastIO();
long long n, m, s, t, u, v;
cin >> n >> m >> s >> t >> u >> v;
for (int i = 1; i <= m; ++i)
{
long long x, y, w;
cin >> x >> y >> w;
g[x].push_back({y, w});
g[y].push_back({x, w});
}
dijkstra1(u, du);
dijkstra1(v, dv);
ans = du[v];
dijkstra2(s, t);
dijkstra2(t, s);
cout << ans << endl;
return 0;
}
Compilation message
commuter_pass.cpp: In function 'void dijkstra1(long long int, long long int*)':
commuter_pass.cpp:40:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
40 | for (auto [v, w] : g[node])
| ^
commuter_pass.cpp: In function 'void dijkstra2(long long int, long long int)':
commuter_pass.cpp:80:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
80 | for (auto [v, w] : g[node])
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
322 ms |
22688 KB |
Output is correct |
2 |
Correct |
289 ms |
22132 KB |
Output is correct |
3 |
Correct |
283 ms |
22148 KB |
Output is correct |
4 |
Correct |
323 ms |
26208 KB |
Output is correct |
5 |
Correct |
294 ms |
25060 KB |
Output is correct |
6 |
Correct |
333 ms |
26612 KB |
Output is correct |
7 |
Correct |
304 ms |
25492 KB |
Output is correct |
8 |
Correct |
302 ms |
25368 KB |
Output is correct |
9 |
Correct |
357 ms |
26524 KB |
Output is correct |
10 |
Correct |
293 ms |
26480 KB |
Output is correct |
11 |
Correct |
112 ms |
13900 KB |
Output is correct |
12 |
Correct |
352 ms |
26524 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
307 ms |
22204 KB |
Output is correct |
2 |
Correct |
314 ms |
21752 KB |
Output is correct |
3 |
Correct |
313 ms |
21612 KB |
Output is correct |
4 |
Correct |
284 ms |
21700 KB |
Output is correct |
5 |
Correct |
321 ms |
21628 KB |
Output is correct |
6 |
Correct |
297 ms |
22000 KB |
Output is correct |
7 |
Correct |
344 ms |
25100 KB |
Output is correct |
8 |
Correct |
340 ms |
25240 KB |
Output is correct |
9 |
Correct |
332 ms |
25132 KB |
Output is correct |
10 |
Correct |
351 ms |
25160 KB |
Output is correct |
11 |
Correct |
119 ms |
13964 KB |
Output is correct |
12 |
Correct |
331 ms |
25876 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
7952 KB |
Output is correct |
2 |
Correct |
5 ms |
5844 KB |
Output is correct |
3 |
Correct |
3 ms |
5844 KB |
Output is correct |
4 |
Correct |
31 ms |
10744 KB |
Output is correct |
5 |
Correct |
17 ms |
8768 KB |
Output is correct |
6 |
Correct |
4 ms |
5972 KB |
Output is correct |
7 |
Correct |
5 ms |
6100 KB |
Output is correct |
8 |
Correct |
6 ms |
6224 KB |
Output is correct |
9 |
Correct |
4 ms |
5972 KB |
Output is correct |
10 |
Correct |
19 ms |
8356 KB |
Output is correct |
11 |
Correct |
4 ms |
5844 KB |
Output is correct |
12 |
Correct |
3 ms |
5880 KB |
Output is correct |
13 |
Correct |
4 ms |
5972 KB |
Output is correct |
14 |
Correct |
4 ms |
5972 KB |
Output is correct |
15 |
Correct |
4 ms |
5972 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
322 ms |
22688 KB |
Output is correct |
2 |
Correct |
289 ms |
22132 KB |
Output is correct |
3 |
Correct |
283 ms |
22148 KB |
Output is correct |
4 |
Correct |
323 ms |
26208 KB |
Output is correct |
5 |
Correct |
294 ms |
25060 KB |
Output is correct |
6 |
Correct |
333 ms |
26612 KB |
Output is correct |
7 |
Correct |
304 ms |
25492 KB |
Output is correct |
8 |
Correct |
302 ms |
25368 KB |
Output is correct |
9 |
Correct |
357 ms |
26524 KB |
Output is correct |
10 |
Correct |
293 ms |
26480 KB |
Output is correct |
11 |
Correct |
112 ms |
13900 KB |
Output is correct |
12 |
Correct |
352 ms |
26524 KB |
Output is correct |
13 |
Correct |
307 ms |
22204 KB |
Output is correct |
14 |
Correct |
314 ms |
21752 KB |
Output is correct |
15 |
Correct |
313 ms |
21612 KB |
Output is correct |
16 |
Correct |
284 ms |
21700 KB |
Output is correct |
17 |
Correct |
321 ms |
21628 KB |
Output is correct |
18 |
Correct |
297 ms |
22000 KB |
Output is correct |
19 |
Correct |
344 ms |
25100 KB |
Output is correct |
20 |
Correct |
340 ms |
25240 KB |
Output is correct |
21 |
Correct |
332 ms |
25132 KB |
Output is correct |
22 |
Correct |
351 ms |
25160 KB |
Output is correct |
23 |
Correct |
119 ms |
13964 KB |
Output is correct |
24 |
Correct |
331 ms |
25876 KB |
Output is correct |
25 |
Correct |
17 ms |
7952 KB |
Output is correct |
26 |
Correct |
5 ms |
5844 KB |
Output is correct |
27 |
Correct |
3 ms |
5844 KB |
Output is correct |
28 |
Correct |
31 ms |
10744 KB |
Output is correct |
29 |
Correct |
17 ms |
8768 KB |
Output is correct |
30 |
Correct |
4 ms |
5972 KB |
Output is correct |
31 |
Correct |
5 ms |
6100 KB |
Output is correct |
32 |
Correct |
6 ms |
6224 KB |
Output is correct |
33 |
Correct |
4 ms |
5972 KB |
Output is correct |
34 |
Correct |
19 ms |
8356 KB |
Output is correct |
35 |
Correct |
4 ms |
5844 KB |
Output is correct |
36 |
Correct |
3 ms |
5880 KB |
Output is correct |
37 |
Correct |
4 ms |
5972 KB |
Output is correct |
38 |
Correct |
4 ms |
5972 KB |
Output is correct |
39 |
Correct |
4 ms |
5972 KB |
Output is correct |
40 |
Correct |
296 ms |
26276 KB |
Output is correct |
41 |
Correct |
309 ms |
26420 KB |
Output is correct |
42 |
Correct |
319 ms |
26444 KB |
Output is correct |
43 |
Correct |
104 ms |
14032 KB |
Output is correct |
44 |
Correct |
143 ms |
14008 KB |
Output is correct |
45 |
Correct |
290 ms |
23144 KB |
Output is correct |
46 |
Correct |
276 ms |
22960 KB |
Output is correct |
47 |
Correct |
329 ms |
25876 KB |
Output is correct |
48 |
Correct |
120 ms |
13448 KB |
Output is correct |
49 |
Correct |
290 ms |
25700 KB |
Output is correct |
50 |
Correct |
308 ms |
23276 KB |
Output is correct |
51 |
Correct |
297 ms |
23200 KB |
Output is correct |