#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define all(x) x.begin(), x.end()
using namespace std;
const int N = 2e5 + 7;
const int MOD = 1e9 + 7; // 998244353;
const int INF = 1e9 + 7;
const long long INFLL = 1e18 + 7;
template <class X, class Y> bool minimize(X &a, Y b) {
if (a > b) return a = b, true;
return false;
}
template <class X, class Y> bool maximize(X &a, Y b) {
if (a < b) return a = b, true;
return false;
}
int n, m, s, t, U, V;
bool can[N];
long long dp[2][N];
vector<int> g[N], f[N];
vector<pair<int, int>> adj[N];
vector<long long> dist_u, dist_v;
vector<long long> dijkstra(int s) {
vector<long long> dist(n + 7, INFLL);
priority_queue<pair<long long, int>> heap;
heap.push(mp(0, s));
dist[s] = 0;
while (!heap.empty()) {
int u; long long d_u;
tie(d_u, u) = heap.top(); heap.pop();
d_u = -d_u;
if (dist[u] != d_u) continue;
for (pair<int, int> v: adj[u]) if (minimize(dist[v.fi], v.se + d_u)) {
heap.push(mp(-dist[v.fi], v.fi));
}
}
return dist;
}
void dfs1(int u) {
dp[0][u] = dist_v[u];
for (int v: g[u]) {
if (dp[0][v] == -1) dfs1(v);
minimize(dp[0][u], dp[0][v]);
}
}
void dfs2(int u) {
dp[1][u] = dist_v[u];
for (int v: f[u]) {
if (dp[1][v] == -1) dfs2(v);
minimize(dp[1][u], dp[1][v]);
}
}
void solve(void) {
cin >> n >> m >> s >> t >> U >> V;
for (int i = 1; i <= m; i ++) {
int u, v, c; cin >> u >> v >> c;
adj[u].emplace_back(v, c);
adj[v].emplace_back(u, c);
}
dist_u = dijkstra(U);
dist_v = dijkstra(V);
vector<long long> dist(dijkstra(s));
vector<long long> _dist(dijkstra(t));
for (int u = 1; u <= n; u ++) {
for (pair<int, int> v: adj[u]) {
if (_dist[v.fi] + v.se + dist[u] == dist[t]) {
can[v.fi] = can[u] = true;
g[u].push_back(v.fi);
f[v.fi].push_back(u);
}
}
}
memset(dp, -1, sizeof dp);
dfs1(s);
dfs2(t);
long long res = dist_u[V];
for (int i = 1; i <= n; i ++) if (can[i]) {
minimize(res, dist_u[i] + min(dp[0][i], dp[1][i]));
}
cout << res;
}
int main(void) {
cin.tie(0)->sync_with_stdio(0);
int test = 1;
// cin >> test;
while (test --) {
solve();
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
249 ms |
27092 KB |
Output is correct |
2 |
Correct |
271 ms |
28432 KB |
Output is correct |
3 |
Correct |
284 ms |
37404 KB |
Output is correct |
4 |
Correct |
236 ms |
32832 KB |
Output is correct |
5 |
Correct |
263 ms |
33192 KB |
Output is correct |
6 |
Correct |
252 ms |
30860 KB |
Output is correct |
7 |
Correct |
304 ms |
34172 KB |
Output is correct |
8 |
Correct |
270 ms |
33340 KB |
Output is correct |
9 |
Correct |
242 ms |
31308 KB |
Output is correct |
10 |
Correct |
214 ms |
31636 KB |
Output is correct |
11 |
Correct |
116 ms |
30400 KB |
Output is correct |
12 |
Correct |
263 ms |
31228 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
300 ms |
29676 KB |
Output is correct |
2 |
Correct |
291 ms |
29992 KB |
Output is correct |
3 |
Correct |
274 ms |
29248 KB |
Output is correct |
4 |
Correct |
287 ms |
29988 KB |
Output is correct |
5 |
Correct |
275 ms |
30544 KB |
Output is correct |
6 |
Correct |
267 ms |
33040 KB |
Output is correct |
7 |
Correct |
301 ms |
33728 KB |
Output is correct |
8 |
Correct |
265 ms |
29900 KB |
Output is correct |
9 |
Correct |
283 ms |
30604 KB |
Output is correct |
10 |
Correct |
278 ms |
29420 KB |
Output is correct |
11 |
Correct |
121 ms |
30660 KB |
Output is correct |
12 |
Correct |
278 ms |
33412 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
18264 KB |
Output is correct |
2 |
Correct |
9 ms |
17492 KB |
Output is correct |
3 |
Correct |
9 ms |
17484 KB |
Output is correct |
4 |
Correct |
19 ms |
19660 KB |
Output is correct |
5 |
Correct |
14 ms |
18524 KB |
Output is correct |
6 |
Correct |
9 ms |
17612 KB |
Output is correct |
7 |
Correct |
10 ms |
17612 KB |
Output is correct |
8 |
Correct |
11 ms |
17612 KB |
Output is correct |
9 |
Correct |
10 ms |
17628 KB |
Output is correct |
10 |
Correct |
14 ms |
18516 KB |
Output is correct |
11 |
Correct |
9 ms |
17484 KB |
Output is correct |
12 |
Correct |
9 ms |
17536 KB |
Output is correct |
13 |
Correct |
9 ms |
17484 KB |
Output is correct |
14 |
Correct |
10 ms |
17484 KB |
Output is correct |
15 |
Correct |
9 ms |
17612 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
249 ms |
27092 KB |
Output is correct |
2 |
Correct |
271 ms |
28432 KB |
Output is correct |
3 |
Correct |
284 ms |
37404 KB |
Output is correct |
4 |
Correct |
236 ms |
32832 KB |
Output is correct |
5 |
Correct |
263 ms |
33192 KB |
Output is correct |
6 |
Correct |
252 ms |
30860 KB |
Output is correct |
7 |
Correct |
304 ms |
34172 KB |
Output is correct |
8 |
Correct |
270 ms |
33340 KB |
Output is correct |
9 |
Correct |
242 ms |
31308 KB |
Output is correct |
10 |
Correct |
214 ms |
31636 KB |
Output is correct |
11 |
Correct |
116 ms |
30400 KB |
Output is correct |
12 |
Correct |
263 ms |
31228 KB |
Output is correct |
13 |
Correct |
300 ms |
29676 KB |
Output is correct |
14 |
Correct |
291 ms |
29992 KB |
Output is correct |
15 |
Correct |
274 ms |
29248 KB |
Output is correct |
16 |
Correct |
287 ms |
29988 KB |
Output is correct |
17 |
Correct |
275 ms |
30544 KB |
Output is correct |
18 |
Correct |
267 ms |
33040 KB |
Output is correct |
19 |
Correct |
301 ms |
33728 KB |
Output is correct |
20 |
Correct |
265 ms |
29900 KB |
Output is correct |
21 |
Correct |
283 ms |
30604 KB |
Output is correct |
22 |
Correct |
278 ms |
29420 KB |
Output is correct |
23 |
Correct |
121 ms |
30660 KB |
Output is correct |
24 |
Correct |
278 ms |
33412 KB |
Output is correct |
25 |
Correct |
14 ms |
18264 KB |
Output is correct |
26 |
Correct |
9 ms |
17492 KB |
Output is correct |
27 |
Correct |
9 ms |
17484 KB |
Output is correct |
28 |
Correct |
19 ms |
19660 KB |
Output is correct |
29 |
Correct |
14 ms |
18524 KB |
Output is correct |
30 |
Correct |
9 ms |
17612 KB |
Output is correct |
31 |
Correct |
10 ms |
17612 KB |
Output is correct |
32 |
Correct |
11 ms |
17612 KB |
Output is correct |
33 |
Correct |
10 ms |
17628 KB |
Output is correct |
34 |
Correct |
14 ms |
18516 KB |
Output is correct |
35 |
Correct |
9 ms |
17484 KB |
Output is correct |
36 |
Correct |
9 ms |
17536 KB |
Output is correct |
37 |
Correct |
9 ms |
17484 KB |
Output is correct |
38 |
Correct |
10 ms |
17484 KB |
Output is correct |
39 |
Correct |
9 ms |
17612 KB |
Output is correct |
40 |
Correct |
248 ms |
31268 KB |
Output is correct |
41 |
Correct |
250 ms |
31200 KB |
Output is correct |
42 |
Correct |
249 ms |
31300 KB |
Output is correct |
43 |
Correct |
149 ms |
34628 KB |
Output is correct |
44 |
Correct |
141 ms |
34604 KB |
Output is correct |
45 |
Correct |
286 ms |
36340 KB |
Output is correct |
46 |
Correct |
301 ms |
36048 KB |
Output is correct |
47 |
Correct |
255 ms |
30900 KB |
Output is correct |
48 |
Correct |
147 ms |
32472 KB |
Output is correct |
49 |
Correct |
209 ms |
30792 KB |
Output is correct |
50 |
Correct |
276 ms |
35112 KB |
Output is correct |
51 |
Correct |
291 ms |
36252 KB |
Output is correct |