#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define dbg(x) cerr << #x << ": " << x << endl;
const ll INF = 1e18;
const int MAX_N = 1e5 + 5;
vector<pair<int, int>> g[MAX_N];
vector<int> new_g[MAX_N];
ll dp[2][MAX_N];
ll dist[4][MAX_N];
void dfs_order(int v, vector<int>& order, vector<bool>& used) {
used[v] = true;
for (auto u : new_g[v]) {
if (!used[u]) {
dfs_order(u, order, used);
}
}
order.push_back(v);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
int s1, t1;
cin >> s1 >> t1;
--s1, --t1;
int s2, t2;
cin >> s2 >> t2;
--s2, --t2;
vector<tuple<int, int, int>> edges(m);
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
--u, --v;
int w;
cin >> w;
g[u].emplace_back(v, w);
g[v].emplace_back(u, w);
edges[i] = {u, v, w};
}
{
array<int, 4> start_vertices = {s2, t2, s1, t1};
for (int i = 0; i < 4; ++i) {
int s = start_vertices[i];
fill_n(dist[i], n, INF);
vector<bool> used(n);
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
pq.emplace(0, s);
while (!pq.empty()) {
auto [curr_dist, v] = pq.top();
pq.pop();
if (used[v]) continue;
used[v] = true;
dist[i][v] = curr_dist;
for (const auto& [u, w] : g[v]) {
if (used[u] || curr_dist + w >= dist[i][u]) continue;
dist[i][u] = curr_dist + w;
pq.emplace(dist[i][u], u);
}
}
}
}
{
for (auto [u, v, w] : edges) {
for (int t = 0; t <= 1; ++t) {
if (dist[2][u] + w == dist[2][v] && dist[2][v] + dist[3][v] == dist[2][t1]) {
new_g[u].push_back(v);
}
swap(u, v);
}
}
}
vector<int> order;
{
vector<bool> used(n);
dfs_order(s1, order, used);
reverse(order.begin(), order.end());
}
fill_n(dp[0], n, INF);
fill_n(dp[1], n, INF);
ll ans = dist[0][t2];
for (auto v : order) {
for (int t = 0; t <= 1; ++t) {
dp[t][v] = min(dp[t][v], dist[t][v]);
for (auto u : new_g[v]) {
dp[t][u] = min(dp[t][u], dp[t][v]);
}
ans = min(ans, dp[t][v] + dist[t ^ 1][v]);
}
}
cout << ans << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
258 ms |
23828 KB |
Output is correct |
2 |
Correct |
284 ms |
22596 KB |
Output is correct |
3 |
Correct |
273 ms |
28448 KB |
Output is correct |
4 |
Correct |
226 ms |
24164 KB |
Output is correct |
5 |
Correct |
287 ms |
23456 KB |
Output is correct |
6 |
Correct |
247 ms |
23844 KB |
Output is correct |
7 |
Correct |
241 ms |
23764 KB |
Output is correct |
8 |
Correct |
243 ms |
23532 KB |
Output is correct |
9 |
Correct |
273 ms |
22976 KB |
Output is correct |
10 |
Correct |
224 ms |
22880 KB |
Output is correct |
11 |
Correct |
89 ms |
20192 KB |
Output is correct |
12 |
Correct |
249 ms |
22780 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
241 ms |
24192 KB |
Output is correct |
2 |
Correct |
283 ms |
24496 KB |
Output is correct |
3 |
Correct |
274 ms |
23828 KB |
Output is correct |
4 |
Correct |
269 ms |
24392 KB |
Output is correct |
5 |
Correct |
261 ms |
25176 KB |
Output is correct |
6 |
Correct |
242 ms |
27632 KB |
Output is correct |
7 |
Correct |
280 ms |
28264 KB |
Output is correct |
8 |
Correct |
269 ms |
24408 KB |
Output is correct |
9 |
Correct |
291 ms |
25160 KB |
Output is correct |
10 |
Correct |
259 ms |
23976 KB |
Output is correct |
11 |
Correct |
100 ms |
22308 KB |
Output is correct |
12 |
Correct |
271 ms |
28048 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
6356 KB |
Output is correct |
2 |
Correct |
3 ms |
5076 KB |
Output is correct |
3 |
Correct |
3 ms |
5076 KB |
Output is correct |
4 |
Correct |
16 ms |
7640 KB |
Output is correct |
5 |
Correct |
10 ms |
6316 KB |
Output is correct |
6 |
Correct |
3 ms |
5164 KB |
Output is correct |
7 |
Correct |
5 ms |
5204 KB |
Output is correct |
8 |
Correct |
4 ms |
5204 KB |
Output is correct |
9 |
Correct |
4 ms |
5076 KB |
Output is correct |
10 |
Correct |
9 ms |
6336 KB |
Output is correct |
11 |
Correct |
3 ms |
5076 KB |
Output is correct |
12 |
Correct |
3 ms |
5076 KB |
Output is correct |
13 |
Correct |
4 ms |
5032 KB |
Output is correct |
14 |
Correct |
4 ms |
5100 KB |
Output is correct |
15 |
Correct |
3 ms |
5076 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
258 ms |
23828 KB |
Output is correct |
2 |
Correct |
284 ms |
22596 KB |
Output is correct |
3 |
Correct |
273 ms |
28448 KB |
Output is correct |
4 |
Correct |
226 ms |
24164 KB |
Output is correct |
5 |
Correct |
287 ms |
23456 KB |
Output is correct |
6 |
Correct |
247 ms |
23844 KB |
Output is correct |
7 |
Correct |
241 ms |
23764 KB |
Output is correct |
8 |
Correct |
243 ms |
23532 KB |
Output is correct |
9 |
Correct |
273 ms |
22976 KB |
Output is correct |
10 |
Correct |
224 ms |
22880 KB |
Output is correct |
11 |
Correct |
89 ms |
20192 KB |
Output is correct |
12 |
Correct |
249 ms |
22780 KB |
Output is correct |
13 |
Correct |
241 ms |
24192 KB |
Output is correct |
14 |
Correct |
283 ms |
24496 KB |
Output is correct |
15 |
Correct |
274 ms |
23828 KB |
Output is correct |
16 |
Correct |
269 ms |
24392 KB |
Output is correct |
17 |
Correct |
261 ms |
25176 KB |
Output is correct |
18 |
Correct |
242 ms |
27632 KB |
Output is correct |
19 |
Correct |
280 ms |
28264 KB |
Output is correct |
20 |
Correct |
269 ms |
24408 KB |
Output is correct |
21 |
Correct |
291 ms |
25160 KB |
Output is correct |
22 |
Correct |
259 ms |
23976 KB |
Output is correct |
23 |
Correct |
100 ms |
22308 KB |
Output is correct |
24 |
Correct |
271 ms |
28048 KB |
Output is correct |
25 |
Correct |
10 ms |
6356 KB |
Output is correct |
26 |
Correct |
3 ms |
5076 KB |
Output is correct |
27 |
Correct |
3 ms |
5076 KB |
Output is correct |
28 |
Correct |
16 ms |
7640 KB |
Output is correct |
29 |
Correct |
10 ms |
6316 KB |
Output is correct |
30 |
Correct |
3 ms |
5164 KB |
Output is correct |
31 |
Correct |
5 ms |
5204 KB |
Output is correct |
32 |
Correct |
4 ms |
5204 KB |
Output is correct |
33 |
Correct |
4 ms |
5076 KB |
Output is correct |
34 |
Correct |
9 ms |
6336 KB |
Output is correct |
35 |
Correct |
3 ms |
5076 KB |
Output is correct |
36 |
Correct |
3 ms |
5076 KB |
Output is correct |
37 |
Correct |
4 ms |
5032 KB |
Output is correct |
38 |
Correct |
4 ms |
5100 KB |
Output is correct |
39 |
Correct |
3 ms |
5076 KB |
Output is correct |
40 |
Correct |
234 ms |
24180 KB |
Output is correct |
41 |
Correct |
275 ms |
22932 KB |
Output is correct |
42 |
Correct |
248 ms |
22856 KB |
Output is correct |
43 |
Correct |
123 ms |
22804 KB |
Output is correct |
44 |
Correct |
141 ms |
22860 KB |
Output is correct |
45 |
Correct |
243 ms |
25400 KB |
Output is correct |
46 |
Correct |
299 ms |
25136 KB |
Output is correct |
47 |
Correct |
251 ms |
23552 KB |
Output is correct |
48 |
Correct |
111 ms |
20272 KB |
Output is correct |
49 |
Correct |
225 ms |
23676 KB |
Output is correct |
50 |
Correct |
282 ms |
24572 KB |
Output is correct |
51 |
Correct |
256 ms |
25380 KB |
Output is correct |