#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mxn = 100 * 1000 + 3, inf = 1e18;
vector<array<int, 2>> g[mxn];
vector<int> par[mxn], dpchild[mxn];
int n, m;
vector<int> dij(int src) {
vector<int> dt(n + 1, inf);
dt[src] = 0;
priority_queue<array<int, 2>, vector<array<int, 2>>, greater<>> pq;
pq.push({0, src});
while(!pq.empty()) {
auto [wt, u] = pq.top();
pq.pop();
if(dt[u] != wt) continue;
for(auto [v, w] : g[u]) {
if(dt[u] + w < dt[v]) {
dt[v] = dt[u] + w;
pq.push({dt[v], v});
}
}
}
return dt;
}
vector<int> dijk(int src) {
vector<int> dt(n + 1, inf);
dt[src] = 0;
priority_queue<array<int, 2>, vector<array<int, 2>>, greater<>> pq;
pq.push({0, src});
while(!pq.empty()) {
auto [wt, v] = pq.top(); pq.pop();
if(dt[v] != wt) continue;
for(auto [u, w] : g[v]) {
if(dt[v] + w < dt[u]) {
dt[u] = dt[v] + w;
pq.push({dt[u], u});
par[u].clear(); par[u].push_back(v);
} else if(dt[v] + w == dt[u])
par[u].push_back(v);
}
}
return dt;
}
vector<bool> reach(int src) {
vector<bool> reachable(n + 1);
queue<int> q; q.push(src);
while (!q.empty()) {
int u = q.front(); q.pop();
if (!reachable[u]) {
reachable[u] = true;
for(int v : par[u]) {
dpchild[v].push_back(u);
q.push(v);
}
}
}
return reachable;
}
signed main() {
std::ios::sync_with_stdio(0);
std::cout.tie(0);
std::cin.tie(0);
#ifdef saarang
freopen("/home/saarang/Documents/cp/input.txt", "r", stdin);
freopen("/home/saarang/Documents/cp/output.txt", "w", stdout);
#endif
int s, t, u, v;
cin >> n >> m >> s >> t >> u >> v;
for(int u1, v1, w, i = 0; i < m; i++) {
cin >> u1 >> v1 >> w;
g[u1].push_back({v1, w});
g[v1].push_back({u1, w});
}
vector<int> du = dij(u), dv = dij(v), ds = dijk(s);
vector<bool> reachable = reach(t);
vector<int> memo(n + 1, -1), memo2(n + 1, -1);
function<int(int v1)> dp = [&] (int v1) {
if(memo[v1] != -1) return memo[v1];
memo[v1] = dv[v1];
for(int u1 : par[v1])
memo[v1] = min(memo[v1], dp(u1));
return memo[v1];
};
function<int(int v1)> dpback = [&] (int v1) {
if(memo2[v1] != -1) return memo2[v1];
memo2[v1] = dv[v1];
for(int u1 : dpchild[v1])
memo2[v1] = min(memo2[v1], dpback(u1));
return memo2[v1];
};
int ans = du[v];
for(int i = 1; i <= n; i++)
if(reachable[i])
ans = min(ans, du[i] + min(dp(i), dpback(i)));
cout << ans << '\n';
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
328 ms |
24816 KB |
Output is correct |
2 |
Correct |
353 ms |
25440 KB |
Output is correct |
3 |
Correct |
381 ms |
28748 KB |
Output is correct |
4 |
Correct |
332 ms |
24524 KB |
Output is correct |
5 |
Correct |
364 ms |
26236 KB |
Output is correct |
6 |
Correct |
349 ms |
24464 KB |
Output is correct |
7 |
Correct |
370 ms |
26248 KB |
Output is correct |
8 |
Correct |
376 ms |
26232 KB |
Output is correct |
9 |
Correct |
330 ms |
24168 KB |
Output is correct |
10 |
Correct |
293 ms |
24272 KB |
Output is correct |
11 |
Correct |
161 ms |
23020 KB |
Output is correct |
12 |
Correct |
337 ms |
24224 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
367 ms |
27144 KB |
Output is correct |
2 |
Correct |
379 ms |
26664 KB |
Output is correct |
3 |
Correct |
380 ms |
26700 KB |
Output is correct |
4 |
Correct |
387 ms |
27108 KB |
Output is correct |
5 |
Correct |
385 ms |
26788 KB |
Output is correct |
6 |
Correct |
371 ms |
29044 KB |
Output is correct |
7 |
Correct |
396 ms |
29352 KB |
Output is correct |
8 |
Correct |
369 ms |
26152 KB |
Output is correct |
9 |
Correct |
374 ms |
26772 KB |
Output is correct |
10 |
Correct |
371 ms |
26536 KB |
Output is correct |
11 |
Correct |
168 ms |
24812 KB |
Output is correct |
12 |
Correct |
368 ms |
28832 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
8940 KB |
Output is correct |
2 |
Correct |
6 ms |
7404 KB |
Output is correct |
3 |
Correct |
6 ms |
7404 KB |
Output is correct |
4 |
Correct |
22 ms |
10220 KB |
Output is correct |
5 |
Correct |
14 ms |
8812 KB |
Output is correct |
6 |
Correct |
6 ms |
7532 KB |
Output is correct |
7 |
Correct |
9 ms |
7532 KB |
Output is correct |
8 |
Correct |
7 ms |
7532 KB |
Output is correct |
9 |
Correct |
7 ms |
7532 KB |
Output is correct |
10 |
Correct |
13 ms |
8812 KB |
Output is correct |
11 |
Correct |
6 ms |
7404 KB |
Output is correct |
12 |
Correct |
6 ms |
7404 KB |
Output is correct |
13 |
Correct |
6 ms |
7404 KB |
Output is correct |
14 |
Correct |
6 ms |
7404 KB |
Output is correct |
15 |
Correct |
6 ms |
7532 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
328 ms |
24816 KB |
Output is correct |
2 |
Correct |
353 ms |
25440 KB |
Output is correct |
3 |
Correct |
381 ms |
28748 KB |
Output is correct |
4 |
Correct |
332 ms |
24524 KB |
Output is correct |
5 |
Correct |
364 ms |
26236 KB |
Output is correct |
6 |
Correct |
349 ms |
24464 KB |
Output is correct |
7 |
Correct |
370 ms |
26248 KB |
Output is correct |
8 |
Correct |
376 ms |
26232 KB |
Output is correct |
9 |
Correct |
330 ms |
24168 KB |
Output is correct |
10 |
Correct |
293 ms |
24272 KB |
Output is correct |
11 |
Correct |
161 ms |
23020 KB |
Output is correct |
12 |
Correct |
337 ms |
24224 KB |
Output is correct |
13 |
Correct |
367 ms |
27144 KB |
Output is correct |
14 |
Correct |
379 ms |
26664 KB |
Output is correct |
15 |
Correct |
380 ms |
26700 KB |
Output is correct |
16 |
Correct |
387 ms |
27108 KB |
Output is correct |
17 |
Correct |
385 ms |
26788 KB |
Output is correct |
18 |
Correct |
371 ms |
29044 KB |
Output is correct |
19 |
Correct |
396 ms |
29352 KB |
Output is correct |
20 |
Correct |
369 ms |
26152 KB |
Output is correct |
21 |
Correct |
374 ms |
26772 KB |
Output is correct |
22 |
Correct |
371 ms |
26536 KB |
Output is correct |
23 |
Correct |
168 ms |
24812 KB |
Output is correct |
24 |
Correct |
368 ms |
28832 KB |
Output is correct |
25 |
Correct |
14 ms |
8940 KB |
Output is correct |
26 |
Correct |
6 ms |
7404 KB |
Output is correct |
27 |
Correct |
6 ms |
7404 KB |
Output is correct |
28 |
Correct |
22 ms |
10220 KB |
Output is correct |
29 |
Correct |
14 ms |
8812 KB |
Output is correct |
30 |
Correct |
6 ms |
7532 KB |
Output is correct |
31 |
Correct |
9 ms |
7532 KB |
Output is correct |
32 |
Correct |
7 ms |
7532 KB |
Output is correct |
33 |
Correct |
7 ms |
7532 KB |
Output is correct |
34 |
Correct |
13 ms |
8812 KB |
Output is correct |
35 |
Correct |
6 ms |
7404 KB |
Output is correct |
36 |
Correct |
6 ms |
7404 KB |
Output is correct |
37 |
Correct |
6 ms |
7404 KB |
Output is correct |
38 |
Correct |
6 ms |
7404 KB |
Output is correct |
39 |
Correct |
6 ms |
7532 KB |
Output is correct |
40 |
Correct |
328 ms |
23504 KB |
Output is correct |
41 |
Correct |
332 ms |
24196 KB |
Output is correct |
42 |
Correct |
327 ms |
24248 KB |
Output is correct |
43 |
Correct |
186 ms |
25324 KB |
Output is correct |
44 |
Correct |
167 ms |
25452 KB |
Output is correct |
45 |
Correct |
418 ms |
28328 KB |
Output is correct |
46 |
Correct |
412 ms |
28348 KB |
Output is correct |
47 |
Correct |
353 ms |
24800 KB |
Output is correct |
48 |
Correct |
193 ms |
23916 KB |
Output is correct |
49 |
Correct |
291 ms |
24592 KB |
Output is correct |
50 |
Correct |
404 ms |
27472 KB |
Output is correct |
51 |
Correct |
417 ms |
28488 KB |
Output is correct |