#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5;
vector<pair<int, ll>> g[N];
vector<ll> ds, dt, du, dv;
int n, m, s, t, u, v;
vector<int> ord;
void work(vector<ll> & d, int st) {
d[st] = 0;
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> q;
q.push({0, st});
while (!q.empty()) {
int x = q.top().second;
ll cd = q.top().first;
q.pop();
if (d[x] < cd) continue;
if (st == s) ord.push_back(x);
for (pair<int, ll> next: g[x]) {
ll nd = next.second + cd;
int nx = next.first;
if (nd < d[nx]) {
d[nx] = nd;
q.push({nd, nx});
}
}
}
}
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m >> s >> t >> u >> v;
s--; t--; u--; v--;
ds = vector<ll>(n, 9e18);
dt = vector<ll>(n, 9e18);
du = vector<ll>(n, 9e18);
dv = vector<ll>(n, 9e18);
for (int i = 0; i < m; ++i) {
int x, y; ll w;
cin >> x >> y >> w;
x--; y--;
g[x].push_back({y, w});
g[y].push_back({x, w});
}
work(ds, s);
work(dt, t);
work(du, u);
work(dv, v);
assert(ds[t] == dt[s]);
assert(du[v] == dv[u]);
vector<ll> dpu(n, 9e18), dpv(n, 9e18);
vector<int> vis(n, 0);
ll ans = du[v];
for (auto x: ord) {
vis[x] = 1;
if (ds[x] + dt[x] == ds[t]) {
dpu[x] = du[x];
dpv[x] = dv[x];
for (auto last: g[x]) {
int nd = last.first;
if (vis[nd] && ds[nd] + dt[nd] == ds[t]) {
dpu[x] = min(dpu[x], dpu[nd]);
dpv[x] = min(dpv[x], dpv[nd]);
}
}
ans = min(ans, dpu[x] + dv[x]);
ans = min(ans, dpv[x] + du[x]);
}
}
cout << ans << "\n";
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
196 ms |
20984 KB |
Output is correct |
2 |
Correct |
219 ms |
19528 KB |
Output is correct |
3 |
Correct |
258 ms |
19564 KB |
Output is correct |
4 |
Correct |
201 ms |
20536 KB |
Output is correct |
5 |
Correct |
188 ms |
19188 KB |
Output is correct |
6 |
Correct |
197 ms |
20520 KB |
Output is correct |
7 |
Correct |
203 ms |
19796 KB |
Output is correct |
8 |
Correct |
191 ms |
19620 KB |
Output is correct |
9 |
Correct |
185 ms |
19296 KB |
Output is correct |
10 |
Correct |
148 ms |
19044 KB |
Output is correct |
11 |
Correct |
61 ms |
13764 KB |
Output is correct |
12 |
Correct |
245 ms |
19424 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
192 ms |
18612 KB |
Output is correct |
2 |
Correct |
205 ms |
18660 KB |
Output is correct |
3 |
Correct |
237 ms |
18764 KB |
Output is correct |
4 |
Correct |
224 ms |
18632 KB |
Output is correct |
5 |
Correct |
200 ms |
18644 KB |
Output is correct |
6 |
Correct |
207 ms |
18740 KB |
Output is correct |
7 |
Correct |
209 ms |
18564 KB |
Output is correct |
8 |
Correct |
225 ms |
18668 KB |
Output is correct |
9 |
Correct |
226 ms |
18820 KB |
Output is correct |
10 |
Correct |
223 ms |
18660 KB |
Output is correct |
11 |
Correct |
63 ms |
13528 KB |
Output is correct |
12 |
Correct |
216 ms |
18860 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
4196 KB |
Output is correct |
2 |
Correct |
2 ms |
2664 KB |
Output is correct |
3 |
Correct |
2 ms |
2664 KB |
Output is correct |
4 |
Correct |
10 ms |
5560 KB |
Output is correct |
5 |
Correct |
7 ms |
4200 KB |
Output is correct |
6 |
Correct |
1 ms |
2920 KB |
Output is correct |
7 |
Correct |
2 ms |
2920 KB |
Output is correct |
8 |
Correct |
2 ms |
2920 KB |
Output is correct |
9 |
Correct |
1 ms |
2916 KB |
Output is correct |
10 |
Correct |
6 ms |
4200 KB |
Output is correct |
11 |
Correct |
1 ms |
2664 KB |
Output is correct |
12 |
Correct |
1 ms |
2664 KB |
Output is correct |
13 |
Correct |
2 ms |
2664 KB |
Output is correct |
14 |
Correct |
2 ms |
2664 KB |
Output is correct |
15 |
Correct |
2 ms |
2664 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
196 ms |
20984 KB |
Output is correct |
2 |
Correct |
219 ms |
19528 KB |
Output is correct |
3 |
Correct |
258 ms |
19564 KB |
Output is correct |
4 |
Correct |
201 ms |
20536 KB |
Output is correct |
5 |
Correct |
188 ms |
19188 KB |
Output is correct |
6 |
Correct |
197 ms |
20520 KB |
Output is correct |
7 |
Correct |
203 ms |
19796 KB |
Output is correct |
8 |
Correct |
191 ms |
19620 KB |
Output is correct |
9 |
Correct |
185 ms |
19296 KB |
Output is correct |
10 |
Correct |
148 ms |
19044 KB |
Output is correct |
11 |
Correct |
61 ms |
13764 KB |
Output is correct |
12 |
Correct |
245 ms |
19424 KB |
Output is correct |
13 |
Correct |
192 ms |
18612 KB |
Output is correct |
14 |
Correct |
205 ms |
18660 KB |
Output is correct |
15 |
Correct |
237 ms |
18764 KB |
Output is correct |
16 |
Correct |
224 ms |
18632 KB |
Output is correct |
17 |
Correct |
200 ms |
18644 KB |
Output is correct |
18 |
Correct |
207 ms |
18740 KB |
Output is correct |
19 |
Correct |
209 ms |
18564 KB |
Output is correct |
20 |
Correct |
225 ms |
18668 KB |
Output is correct |
21 |
Correct |
226 ms |
18820 KB |
Output is correct |
22 |
Correct |
223 ms |
18660 KB |
Output is correct |
23 |
Correct |
63 ms |
13528 KB |
Output is correct |
24 |
Correct |
216 ms |
18860 KB |
Output is correct |
25 |
Correct |
6 ms |
4196 KB |
Output is correct |
26 |
Correct |
2 ms |
2664 KB |
Output is correct |
27 |
Correct |
2 ms |
2664 KB |
Output is correct |
28 |
Correct |
10 ms |
5560 KB |
Output is correct |
29 |
Correct |
7 ms |
4200 KB |
Output is correct |
30 |
Correct |
1 ms |
2920 KB |
Output is correct |
31 |
Correct |
2 ms |
2920 KB |
Output is correct |
32 |
Correct |
2 ms |
2920 KB |
Output is correct |
33 |
Correct |
1 ms |
2916 KB |
Output is correct |
34 |
Correct |
6 ms |
4200 KB |
Output is correct |
35 |
Correct |
1 ms |
2664 KB |
Output is correct |
36 |
Correct |
1 ms |
2664 KB |
Output is correct |
37 |
Correct |
2 ms |
2664 KB |
Output is correct |
38 |
Correct |
2 ms |
2664 KB |
Output is correct |
39 |
Correct |
2 ms |
2664 KB |
Output is correct |
40 |
Correct |
175 ms |
23660 KB |
Output is correct |
41 |
Correct |
224 ms |
22832 KB |
Output is correct |
42 |
Correct |
198 ms |
22984 KB |
Output is correct |
43 |
Correct |
57 ms |
15580 KB |
Output is correct |
44 |
Correct |
56 ms |
15576 KB |
Output is correct |
45 |
Correct |
198 ms |
22216 KB |
Output is correct |
46 |
Correct |
187 ms |
21776 KB |
Output is correct |
47 |
Correct |
185 ms |
23732 KB |
Output is correct |
48 |
Correct |
60 ms |
15064 KB |
Output is correct |
49 |
Correct |
143 ms |
23096 KB |
Output is correct |
50 |
Correct |
200 ms |
22216 KB |
Output is correct |
51 |
Correct |
157 ms |
21960 KB |
Output is correct |