#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
const ll MAXN = 1E5+16, INF = ll(1E18)+16;
vector <pair <ll, ll> > adj[4*MAXN];
ll dis[4*MAXN];
bool vis[4*MAXN];
ll enc (ll u, int graphid) { return ((u<<2)|graphid); } // encode state into number
ll unenc (ll u) { return (u>>2); } // unencode
// graphid:
// 0b00 regular level 0 graph
// 0b01 foward dijkstra dag from u1 to v1 (commuter pass) level 1 graph
// 0b10 reverse dijkstra dag, same as 0b01 (commuter pass) level 1 graph
// 0b11 regular graph, same as 0b00, level 2 graph
int main () {
cin.tie(nullptr) -> sync_with_stdio(false);
ll n, m;
cin >> n >> m;
ll u1, v1, u2, v2;
cin >> u1 >> v1 >> u2 >> v2;
u1--; v1--; u2--; v2--;
auto addEdge = [&](ll u, ll v, ll w) { adj[u].push_back({ v, w }); };
for (ll i = 0; i < m; i++) {
ll u, v, w;
cin >> u >> v >> w;
u--; v--;
addEdge(enc(u, 0b00), enc(v, 0b00), w); // reg graph 1 (0b00)
addEdge(enc(v, 0b00), enc(u, 0b00), w);
addEdge(enc(u, 0b11), enc(v, 0b11), w); // reg graph 2 (0b11)
addEdge(enc(v, 0b11), enc(u, 0b11), w);
}
{priority_queue <pair <ll, ll> > pq;
for (ll i = 0; i < 4*MAXN; i++) dis[i] = INF;
for (ll i = 0; i < 4*MAXN; i++) vis[i] = false;
dis[enc(u1, 0b00)] = 0;
pq.push({ -dis[enc(u1, 0b00)], enc(u1, 0b00) });
while (pq.size()) {
ll u = pq.top().second; pq.pop();
if (u == enc(v1, 0b00)) break;
if (vis[u]) continue;
vis[u] = true;
for (auto [v, w] : adj[u]) {
if (dis[v] <= dis[u]+w) continue;
dis[v] = dis[u]+w;
pq.push({ -dis[v], v });
}
}
for (ll i = 0; i < 4*MAXN; i++) vis[i] = false;
function <void(ll)> dfs = [&](ll u) {
if (vis[u]) return;
vis[u] = true;
for (auto [v, w] : adj[u]) {
if (dis[v]+w != dis[u]) continue;
// cerr << unenc(v)+1 << ' ' << unenc(u)+1 << '\n';
addEdge(enc(unenc(v), 0b01), enc(unenc(u), 0b01), 0); // dag fow (0b01)
addEdge(enc(unenc(u), 0b10), enc(unenc(v), 0b10), 0); // dag rev (0b10)
dfs(v);
}
};
dfs(enc(v1, 0b00));}
for (ll u = 0; u < n; u++) { // transitions between graphs
addEdge(enc(u, 0b00), enc(u, 0b01), 0); // 0b00 to dag fow (0b01)
addEdge(enc(u, 0b00), enc(u, 0b10), 0); // 0b00 to dag rev (0b10)
addEdge(enc(u, 0b01), enc(u, 0b11), 0); // 0b01 to reg graph 2 (0b11)
addEdge(enc(u, 0b10), enc(u, 0b11), 0); // 0b10 to reg graph 2 (0b11)
}
{priority_queue <pair <ll, ll> > pq;
for (ll i = 0; i < 4*MAXN; i++) dis[i] = INF;
for (ll i = 0; i < 4*MAXN; i++) vis[i] = false;
dis[enc(u2, 0b00)] = 0;
pq.push({ -dis[enc(u2, 0b00)], enc(u2, 0b00) });
while (pq.size()) {
ll u = pq.top().second; pq.pop();
if (vis[u]) continue;
vis[u] = true;
for (auto [v, w] : adj[u]) {
if (dis[v] <= dis[u]+w) continue;
dis[v] = dis[u]+w;
pq.push({ -dis[v], v });
}
}
cout << dis[enc(v2, 0b11)] << '\n';}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
328 ms |
50924 KB |
Output is correct |
2 |
Correct |
358 ms |
47712 KB |
Output is correct |
3 |
Correct |
391 ms |
58444 KB |
Output is correct |
4 |
Correct |
330 ms |
46860 KB |
Output is correct |
5 |
Correct |
382 ms |
48856 KB |
Output is correct |
6 |
Correct |
315 ms |
50840 KB |
Output is correct |
7 |
Correct |
380 ms |
49932 KB |
Output is correct |
8 |
Correct |
387 ms |
52444 KB |
Output is correct |
9 |
Correct |
355 ms |
51244 KB |
Output is correct |
10 |
Correct |
315 ms |
51520 KB |
Output is correct |
11 |
Correct |
182 ms |
41424 KB |
Output is correct |
12 |
Correct |
399 ms |
51336 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
367 ms |
50624 KB |
Output is correct |
2 |
Correct |
377 ms |
54768 KB |
Output is correct |
3 |
Correct |
401 ms |
55280 KB |
Output is correct |
4 |
Correct |
385 ms |
54720 KB |
Output is correct |
5 |
Correct |
432 ms |
55356 KB |
Output is correct |
6 |
Correct |
383 ms |
60768 KB |
Output is correct |
7 |
Correct |
391 ms |
63712 KB |
Output is correct |
8 |
Correct |
401 ms |
54644 KB |
Output is correct |
9 |
Correct |
414 ms |
55524 KB |
Output is correct |
10 |
Correct |
376 ms |
54132 KB |
Output is correct |
11 |
Correct |
202 ms |
45772 KB |
Output is correct |
12 |
Correct |
458 ms |
61516 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
16220 KB |
Output is correct |
2 |
Correct |
3 ms |
13404 KB |
Output is correct |
3 |
Correct |
4 ms |
13404 KB |
Output is correct |
4 |
Correct |
16 ms |
19292 KB |
Output is correct |
5 |
Correct |
10 ms |
16220 KB |
Output is correct |
6 |
Correct |
4 ms |
13404 KB |
Output is correct |
7 |
Correct |
4 ms |
13656 KB |
Output is correct |
8 |
Correct |
5 ms |
13660 KB |
Output is correct |
9 |
Correct |
4 ms |
13400 KB |
Output is correct |
10 |
Correct |
12 ms |
16216 KB |
Output is correct |
11 |
Correct |
3 ms |
13404 KB |
Output is correct |
12 |
Correct |
3 ms |
13404 KB |
Output is correct |
13 |
Correct |
4 ms |
13404 KB |
Output is correct |
14 |
Correct |
4 ms |
13400 KB |
Output is correct |
15 |
Correct |
4 ms |
13400 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
328 ms |
50924 KB |
Output is correct |
2 |
Correct |
358 ms |
47712 KB |
Output is correct |
3 |
Correct |
391 ms |
58444 KB |
Output is correct |
4 |
Correct |
330 ms |
46860 KB |
Output is correct |
5 |
Correct |
382 ms |
48856 KB |
Output is correct |
6 |
Correct |
315 ms |
50840 KB |
Output is correct |
7 |
Correct |
380 ms |
49932 KB |
Output is correct |
8 |
Correct |
387 ms |
52444 KB |
Output is correct |
9 |
Correct |
355 ms |
51244 KB |
Output is correct |
10 |
Correct |
315 ms |
51520 KB |
Output is correct |
11 |
Correct |
182 ms |
41424 KB |
Output is correct |
12 |
Correct |
399 ms |
51336 KB |
Output is correct |
13 |
Correct |
367 ms |
50624 KB |
Output is correct |
14 |
Correct |
377 ms |
54768 KB |
Output is correct |
15 |
Correct |
401 ms |
55280 KB |
Output is correct |
16 |
Correct |
385 ms |
54720 KB |
Output is correct |
17 |
Correct |
432 ms |
55356 KB |
Output is correct |
18 |
Correct |
383 ms |
60768 KB |
Output is correct |
19 |
Correct |
391 ms |
63712 KB |
Output is correct |
20 |
Correct |
401 ms |
54644 KB |
Output is correct |
21 |
Correct |
414 ms |
55524 KB |
Output is correct |
22 |
Correct |
376 ms |
54132 KB |
Output is correct |
23 |
Correct |
202 ms |
45772 KB |
Output is correct |
24 |
Correct |
458 ms |
61516 KB |
Output is correct |
25 |
Correct |
10 ms |
16220 KB |
Output is correct |
26 |
Correct |
3 ms |
13404 KB |
Output is correct |
27 |
Correct |
4 ms |
13404 KB |
Output is correct |
28 |
Correct |
16 ms |
19292 KB |
Output is correct |
29 |
Correct |
10 ms |
16220 KB |
Output is correct |
30 |
Correct |
4 ms |
13404 KB |
Output is correct |
31 |
Correct |
4 ms |
13656 KB |
Output is correct |
32 |
Correct |
5 ms |
13660 KB |
Output is correct |
33 |
Correct |
4 ms |
13400 KB |
Output is correct |
34 |
Correct |
12 ms |
16216 KB |
Output is correct |
35 |
Correct |
3 ms |
13404 KB |
Output is correct |
36 |
Correct |
3 ms |
13404 KB |
Output is correct |
37 |
Correct |
4 ms |
13404 KB |
Output is correct |
38 |
Correct |
4 ms |
13400 KB |
Output is correct |
39 |
Correct |
4 ms |
13400 KB |
Output is correct |
40 |
Correct |
312 ms |
54432 KB |
Output is correct |
41 |
Correct |
308 ms |
50200 KB |
Output is correct |
42 |
Correct |
353 ms |
51184 KB |
Output is correct |
43 |
Correct |
264 ms |
47060 KB |
Output is correct |
44 |
Correct |
255 ms |
47068 KB |
Output is correct |
45 |
Correct |
441 ms |
59328 KB |
Output is correct |
46 |
Correct |
466 ms |
58864 KB |
Output is correct |
47 |
Correct |
352 ms |
50452 KB |
Output is correct |
48 |
Correct |
276 ms |
42648 KB |
Output is correct |
49 |
Correct |
299 ms |
52648 KB |
Output is correct |
50 |
Correct |
462 ms |
56620 KB |
Output is correct |
51 |
Correct |
432 ms |
59380 KB |
Output is correct |