#include <bits/stdc++.h>
#define ll long long
#define ar array
#define db double
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rint(l, r) uniform_int_distribution<int>(l, r)(rng)
template<typename T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
void test_case() {
int n, m;
cin >> n >> m;
int S, T, U, V;
cin >> S >> T >> U >> V;
vector<vector<ar<int, 2>>> adj(n+1);
for (int i = 0; i < m; i++) {
int x, y, w;
cin >> x >> y >> w;
adj[x].push_back({y, w});
adj[y].push_back({x, w});
}
auto cost = [&](int sx) -> vector<ll> {
vector<ll> d(n+1, 1e18);
priority_queue<ar<ll, 2>, vector<ar<ll, 2>>, greater<ar<ll, 2>>> q;
q.push({0, sx});
d[sx] = 0;
while (q.size()) {
auto [weight, v] = q.top(); q.pop();
if (weight != d[v]) continue;
for (auto [u, w] : adj[v]) {
if (ckmin(d[u], d[v] + w)) {
q.push({d[u], u});
}
}
}
return d;
};
vector<ll> ds(cost(S)), dt(cost(T)), du(cost(U)), dv(cost(V));
// sort by order of dv
vector<int> each(n);
iota(all(each), 1);
sort(all(each), [&](int x, int y) { return dv[x] < dv[y]; });
vector<int> where(n+1);
for (int i = 0; i < n; i++) where[each[i]] = i;
ll ans = 1e18, bst = ds[T];
vector<int> dp1(n+1, 1e9), dp2(n+1, 1e9);
vector<int> o1(n);
iota(all(o1), 1);
sort(all(o1), [&](int x, int y) { return ds[x] < ds[y]; });
for (int v : o1) { // v --> s
if (ds[v] + dt[v] != bst) continue;
dp1[v] = where[v];
for (auto [u, w] : adj[v]) {
if (dt[v] + w + ds[u] == bst) {
ckmin(dp1[v], dp1[u]);
}
}
}
sort(all(o1), [&](int x, int y) { return dt[x] < dt[y]; });
for (int v : o1) { // v --> t
if (ds[v] + dt[v] != bst) continue;
dp2[v] = where[v];
for (auto [u, w] : adj[v]) {
if (ds[v] + w + dt[u] == bst) {
ckmin(dp2[v], dp2[u]);
}
}
}
for (int i = 1; i <= n; i++) {
int idx = min(dp1[i], dp2[i]);
if (idx < n) {
ckmin(ans, du[i] + dv[each[idx]]);
}
}
cout << min(ans, du[V]) << '\n';
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int t = 1;
// cin >> t;
while (t--) test_case();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
201 ms |
15348 KB |
Output is correct |
2 |
Correct |
210 ms |
14056 KB |
Output is correct |
3 |
Correct |
216 ms |
17852 KB |
Output is correct |
4 |
Correct |
245 ms |
19044 KB |
Output is correct |
5 |
Correct |
186 ms |
17532 KB |
Output is correct |
6 |
Correct |
209 ms |
20112 KB |
Output is correct |
7 |
Correct |
241 ms |
17508 KB |
Output is correct |
8 |
Correct |
216 ms |
17568 KB |
Output is correct |
9 |
Correct |
195 ms |
18324 KB |
Output is correct |
10 |
Correct |
180 ms |
18536 KB |
Output is correct |
11 |
Correct |
83 ms |
13300 KB |
Output is correct |
12 |
Correct |
218 ms |
18276 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
212 ms |
14132 KB |
Output is correct |
2 |
Correct |
214 ms |
17472 KB |
Output is correct |
3 |
Correct |
231 ms |
17376 KB |
Output is correct |
4 |
Correct |
222 ms |
17360 KB |
Output is correct |
5 |
Correct |
246 ms |
17500 KB |
Output is correct |
6 |
Correct |
198 ms |
17832 KB |
Output is correct |
7 |
Correct |
212 ms |
17376 KB |
Output is correct |
8 |
Correct |
222 ms |
17620 KB |
Output is correct |
9 |
Correct |
209 ms |
17588 KB |
Output is correct |
10 |
Correct |
236 ms |
17620 KB |
Output is correct |
11 |
Correct |
80 ms |
12872 KB |
Output is correct |
12 |
Correct |
234 ms |
17820 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
1116 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
10 ms |
1628 KB |
Output is correct |
5 |
Correct |
5 ms |
1112 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
2 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
5 ms |
1116 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
14 |
Correct |
1 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
201 ms |
15348 KB |
Output is correct |
2 |
Correct |
210 ms |
14056 KB |
Output is correct |
3 |
Correct |
216 ms |
17852 KB |
Output is correct |
4 |
Correct |
245 ms |
19044 KB |
Output is correct |
5 |
Correct |
186 ms |
17532 KB |
Output is correct |
6 |
Correct |
209 ms |
20112 KB |
Output is correct |
7 |
Correct |
241 ms |
17508 KB |
Output is correct |
8 |
Correct |
216 ms |
17568 KB |
Output is correct |
9 |
Correct |
195 ms |
18324 KB |
Output is correct |
10 |
Correct |
180 ms |
18536 KB |
Output is correct |
11 |
Correct |
83 ms |
13300 KB |
Output is correct |
12 |
Correct |
218 ms |
18276 KB |
Output is correct |
13 |
Correct |
212 ms |
14132 KB |
Output is correct |
14 |
Correct |
214 ms |
17472 KB |
Output is correct |
15 |
Correct |
231 ms |
17376 KB |
Output is correct |
16 |
Correct |
222 ms |
17360 KB |
Output is correct |
17 |
Correct |
246 ms |
17500 KB |
Output is correct |
18 |
Correct |
198 ms |
17832 KB |
Output is correct |
19 |
Correct |
212 ms |
17376 KB |
Output is correct |
20 |
Correct |
222 ms |
17620 KB |
Output is correct |
21 |
Correct |
209 ms |
17588 KB |
Output is correct |
22 |
Correct |
236 ms |
17620 KB |
Output is correct |
23 |
Correct |
80 ms |
12872 KB |
Output is correct |
24 |
Correct |
234 ms |
17820 KB |
Output is correct |
25 |
Correct |
6 ms |
1116 KB |
Output is correct |
26 |
Correct |
1 ms |
348 KB |
Output is correct |
27 |
Correct |
1 ms |
348 KB |
Output is correct |
28 |
Correct |
10 ms |
1628 KB |
Output is correct |
29 |
Correct |
5 ms |
1112 KB |
Output is correct |
30 |
Correct |
1 ms |
348 KB |
Output is correct |
31 |
Correct |
1 ms |
348 KB |
Output is correct |
32 |
Correct |
2 ms |
348 KB |
Output is correct |
33 |
Correct |
1 ms |
348 KB |
Output is correct |
34 |
Correct |
5 ms |
1116 KB |
Output is correct |
35 |
Correct |
1 ms |
348 KB |
Output is correct |
36 |
Correct |
1 ms |
348 KB |
Output is correct |
37 |
Correct |
1 ms |
348 KB |
Output is correct |
38 |
Correct |
1 ms |
348 KB |
Output is correct |
39 |
Correct |
1 ms |
344 KB |
Output is correct |
40 |
Correct |
191 ms |
19432 KB |
Output is correct |
41 |
Correct |
197 ms |
18144 KB |
Output is correct |
42 |
Correct |
222 ms |
18388 KB |
Output is correct |
43 |
Correct |
75 ms |
13096 KB |
Output is correct |
44 |
Correct |
75 ms |
13140 KB |
Output is correct |
45 |
Correct |
170 ms |
17720 KB |
Output is correct |
46 |
Correct |
194 ms |
17272 KB |
Output is correct |
47 |
Correct |
203 ms |
18940 KB |
Output is correct |
48 |
Correct |
78 ms |
12368 KB |
Output is correct |
49 |
Correct |
183 ms |
19232 KB |
Output is correct |
50 |
Correct |
201 ms |
17376 KB |
Output is correct |
51 |
Correct |
166 ms |
17448 KB |
Output is correct |