#include <bits/stdc++.h>
using namespace std;
inline namespace
{
} // namespace
void solve()
{
int n, m;
cin >> n >> m;
int s, t, u, v;
cin >> s >> t >> u >> v, --s, --t, --u, --v;
// cerr << s << ' ' << t << '\n';
// cerr << u << ' ' << v << '\n';
vector<vector<pair<int, long>>> adj(n);
for (int i = 0; i < m; i++)
{
int a, b;
long c;
cin >> a >> b >> c, --a, --b;
adj[a].emplace_back(b, c);
adj[b].emplace_back(a, c);
}
vector<vector<int>> gr(n);
{
vector<long> dist(n, LONG_MAX);
priority_queue<pair<long, int>> pq;
vector<vector<int>> gr1(n);
vector<vector<int>> todo(n);
dist[s] = 0;
for (pq.emplace(-dist[s], s); !pq.empty();)
{
auto [d, a] = pq.top();
pq.pop();
if (d != -dist[a])
continue;
for (int b : todo[a])
gr1[a].push_back(b);
for (auto [b, c] : adj[a])
{
if (dist[a] + c < dist[b])
{
todo[b].clear(),
todo[b].push_back(a);
dist[b] = dist[a] + c;
pq.emplace(-dist[b], b);
}
else if (dist[a] + c == dist[b])
todo[b].push_back(a);
}
}
queue<int> q;
vector<bool> done(n, 0);
for (q.push(t); !q.empty();)
{
int a = q.front();
q.pop();
if (done[a])
continue;
done[a] = 1;
for (int b : gr1[a])
{
gr[b].push_back(a);
q.push(b);
}
}
}
long res = LONG_MAX;
{
vector<long> dist_u(n, LONG_MAX), dist_v(n, LONG_MAX);
{
priority_queue<pair<long, int>> pq;
dist_u[u] = 0;
for (pq.emplace(-dist_u[u], u); !pq.empty();)
{
auto [d, a] = pq.top();
pq.pop();
if (d != -dist_u[a])
continue;
for (auto [b, c] : adj[a])
{
if (dist_u[a] + c < dist_u[b])
{
dist_u[b] = dist_u[a] + c;
pq.emplace(-dist_u[b], b);
}
}
}
}
{
priority_queue<pair<long, int>> pq;
dist_v[v] = 0;
for (pq.emplace(-dist_v[v], v); !pq.empty();)
{
auto [d, a] = pq.top();
pq.pop();
if (d != -dist_v[a])
continue;
for (auto [b, c] : adj[a])
{
if (dist_v[a] + c < dist_v[b])
{
dist_v[b] = dist_v[a] + c;
pq.emplace(-dist_v[b], b);
}
}
}
}
res = dist_u[v];
for (int k : {0, 1})
{
vector<int> deg(n);
for (int i = 0; i < n; i++)
{
for (int j : gr[i])
deg[j]++;
}
vector<long> dp = dist_u;
queue<int> q;
for (q.push(s); !q.empty();)
{
int a = q.front();
q.pop();
res = min(res, dp[a] + dist_v[a]);
// cerr << a << ' ' << dp[a] << ' ' << dist_v[a] << '\n';
for (int b : gr[a])
{
dp[b] = min(dp[b], dp[a]);
if (--deg[b] == 0)
q.push(b);
}
}
// cerr << '\n';
swap(u, v), swap(dist_u, dist_v);
}
}
cout << res << '\n';
}
int main()
{
ios_base::sync_with_stdio(false), cin.tie(NULL);
solve();
return 0;
}
Compilation message
commuter_pass.cpp: In function 'void solve()':
commuter_pass.cpp:131:18: warning: unused variable 'k' [-Wunused-variable]
131 | for (int k : {0, 1})
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
319 ms |
28128 KB |
Output is correct |
2 |
Correct |
341 ms |
28972 KB |
Output is correct |
3 |
Correct |
326 ms |
30044 KB |
Output is correct |
4 |
Correct |
303 ms |
28216 KB |
Output is correct |
5 |
Correct |
339 ms |
29716 KB |
Output is correct |
6 |
Correct |
309 ms |
28496 KB |
Output is correct |
7 |
Correct |
358 ms |
30128 KB |
Output is correct |
8 |
Correct |
328 ms |
30012 KB |
Output is correct |
9 |
Correct |
305 ms |
28060 KB |
Output is correct |
10 |
Correct |
264 ms |
27952 KB |
Output is correct |
11 |
Correct |
153 ms |
23824 KB |
Output is correct |
12 |
Correct |
314 ms |
28304 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
325 ms |
29748 KB |
Output is correct |
2 |
Correct |
394 ms |
29108 KB |
Output is correct |
3 |
Correct |
315 ms |
29304 KB |
Output is correct |
4 |
Correct |
364 ms |
29140 KB |
Output is correct |
5 |
Correct |
344 ms |
29596 KB |
Output is correct |
6 |
Correct |
322 ms |
30148 KB |
Output is correct |
7 |
Correct |
340 ms |
30276 KB |
Output is correct |
8 |
Correct |
339 ms |
29236 KB |
Output is correct |
9 |
Correct |
320 ms |
29656 KB |
Output is correct |
10 |
Correct |
354 ms |
29060 KB |
Output is correct |
11 |
Correct |
214 ms |
24444 KB |
Output is correct |
12 |
Correct |
317 ms |
30408 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
2124 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
324 KB |
Output is correct |
4 |
Correct |
16 ms |
3780 KB |
Output is correct |
5 |
Correct |
11 ms |
2004 KB |
Output is correct |
6 |
Correct |
1 ms |
468 KB |
Output is correct |
7 |
Correct |
2 ms |
468 KB |
Output is correct |
8 |
Correct |
2 ms |
596 KB |
Output is correct |
9 |
Correct |
2 ms |
468 KB |
Output is correct |
10 |
Correct |
7 ms |
1992 KB |
Output is correct |
11 |
Correct |
1 ms |
324 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
2 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
2 ms |
328 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
319 ms |
28128 KB |
Output is correct |
2 |
Correct |
341 ms |
28972 KB |
Output is correct |
3 |
Correct |
326 ms |
30044 KB |
Output is correct |
4 |
Correct |
303 ms |
28216 KB |
Output is correct |
5 |
Correct |
339 ms |
29716 KB |
Output is correct |
6 |
Correct |
309 ms |
28496 KB |
Output is correct |
7 |
Correct |
358 ms |
30128 KB |
Output is correct |
8 |
Correct |
328 ms |
30012 KB |
Output is correct |
9 |
Correct |
305 ms |
28060 KB |
Output is correct |
10 |
Correct |
264 ms |
27952 KB |
Output is correct |
11 |
Correct |
153 ms |
23824 KB |
Output is correct |
12 |
Correct |
314 ms |
28304 KB |
Output is correct |
13 |
Correct |
325 ms |
29748 KB |
Output is correct |
14 |
Correct |
394 ms |
29108 KB |
Output is correct |
15 |
Correct |
315 ms |
29304 KB |
Output is correct |
16 |
Correct |
364 ms |
29140 KB |
Output is correct |
17 |
Correct |
344 ms |
29596 KB |
Output is correct |
18 |
Correct |
322 ms |
30148 KB |
Output is correct |
19 |
Correct |
340 ms |
30276 KB |
Output is correct |
20 |
Correct |
339 ms |
29236 KB |
Output is correct |
21 |
Correct |
320 ms |
29656 KB |
Output is correct |
22 |
Correct |
354 ms |
29060 KB |
Output is correct |
23 |
Correct |
214 ms |
24444 KB |
Output is correct |
24 |
Correct |
317 ms |
30408 KB |
Output is correct |
25 |
Correct |
10 ms |
2124 KB |
Output is correct |
26 |
Correct |
1 ms |
332 KB |
Output is correct |
27 |
Correct |
1 ms |
324 KB |
Output is correct |
28 |
Correct |
16 ms |
3780 KB |
Output is correct |
29 |
Correct |
11 ms |
2004 KB |
Output is correct |
30 |
Correct |
1 ms |
468 KB |
Output is correct |
31 |
Correct |
2 ms |
468 KB |
Output is correct |
32 |
Correct |
2 ms |
596 KB |
Output is correct |
33 |
Correct |
2 ms |
468 KB |
Output is correct |
34 |
Correct |
7 ms |
1992 KB |
Output is correct |
35 |
Correct |
1 ms |
324 KB |
Output is correct |
36 |
Correct |
1 ms |
340 KB |
Output is correct |
37 |
Correct |
2 ms |
340 KB |
Output is correct |
38 |
Correct |
1 ms |
340 KB |
Output is correct |
39 |
Correct |
2 ms |
328 KB |
Output is correct |
40 |
Correct |
302 ms |
28572 KB |
Output is correct |
41 |
Correct |
297 ms |
28220 KB |
Output is correct |
42 |
Correct |
308 ms |
29076 KB |
Output is correct |
43 |
Correct |
211 ms |
25608 KB |
Output is correct |
44 |
Correct |
185 ms |
25676 KB |
Output is correct |
45 |
Correct |
347 ms |
31372 KB |
Output is correct |
46 |
Correct |
410 ms |
31276 KB |
Output is correct |
47 |
Correct |
347 ms |
28828 KB |
Output is correct |
48 |
Correct |
167 ms |
25688 KB |
Output is correct |
49 |
Correct |
286 ms |
28200 KB |
Output is correct |
50 |
Correct |
339 ms |
30756 KB |
Output is correct |
51 |
Correct |
408 ms |
31292 KB |
Output is correct |