#include<bits/stdc++.h>
using namespace std;
using LL=long long;
#define FOR(i,l,r) for(int i=(l);i<=(r);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ssize(x) int(x.size())
template<class A,class B>auto&operator<<(ostream&o,pair<A,B>p){return o<<'('<<p.first<<", "<<p.second<<')';}
template<class T>auto operator<<(ostream&o,T x)->decltype(x.end(),o){o<<'{';int i=0;for(auto e:x)o<<(", ")+2*!i++<<e;return o<<'}';}
#ifdef DEBUG
#define debug(x...) cerr<<"["#x"]: ",[](auto...$){((cerr<<$<<"; "),...)<<'\n';}(x)
#else
#define debug(...) {}
#endif
int main() {
cin.tie(0)->sync_with_stdio(0);
const LL INF = 1e18;
int n, m, S, T, U, V;
cin >> n >> m >> S >> T >> U >> V;
--S;
--T;
--U;
--V;
vector<vector<pair<int, int>>> v(n);
REP (i, m) {
int a, b, c;
cin >> a >> b >> c;
--a;
--b;
v[a].emplace_back(b, c);
v[b].emplace_back(a, c);
}
auto wylicz = [&](int st, vector<LL> &odl) {
REP (i, n) {
odl[i] = INF;
}
odl[st] = 0;
priority_queue<pair<LL, int>> pq;
pq.push({0, st});
while (!pq.empty()) {
LL d = -pq.top().first;
int x = pq.top().second;
pq.pop();
if (d != odl[x]) {
continue;
}
for (auto &[a, b] : v[x]) {
if (odl[a] > odl[x] + b) {
odl[a] = odl[x] + b;
pq.push({-odl[a], a});
}
}
}
return odl;
};
vector<LL> odlU(n), odlV(n);
wylicz(U, odlU);
wylicz(V, odlV);
debug(odlU);
debug(odlV);
vector<LL> odl(n, INF);
vector<int> odw(n, 0);
vector<vector<LL>> dp(n, vector<LL> (3, INF));
priority_queue<pair<LL, int>> pq;
pq.push({0, S});
odl[S] = 0;
while (!pq.empty()) {
int x = pq.top().second;
pq.pop();
if (odw[x]) {
continue;
}
odw[x] = 1;
dp[x][2] = min({dp[x][0] + odlV[x], dp[x][1] + odlU[x], odlU[x] + odlV[x], dp[x][2]});
dp[x][0] = min(dp[x][0], odlU[x]);
dp[x][1] = min(dp[x][1], odlV[x]);
for (auto &[a, b] : v[x]) {
if (odl[a] > odl[x] + b) {
odl[a] = odl[x] + b;
pq.push({-odl[a], a});
dp[a] = dp[x];
}
if (odl[a] == odl[x] + b) {
REP (i, 3) {
dp[a][i] = min(dp[a][i], dp[x][i]);
}
}
}
}
debug(dp);
cout << min(dp[T][2], odlU[V]) << endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
241 ms |
19652 KB |
Output is correct |
2 |
Correct |
249 ms |
18560 KB |
Output is correct |
3 |
Correct |
271 ms |
18264 KB |
Output is correct |
4 |
Correct |
258 ms |
22316 KB |
Output is correct |
5 |
Correct |
233 ms |
21804 KB |
Output is correct |
6 |
Correct |
262 ms |
23588 KB |
Output is correct |
7 |
Correct |
244 ms |
22172 KB |
Output is correct |
8 |
Correct |
248 ms |
22136 KB |
Output is correct |
9 |
Correct |
230 ms |
22664 KB |
Output is correct |
10 |
Correct |
215 ms |
22720 KB |
Output is correct |
11 |
Correct |
113 ms |
16048 KB |
Output is correct |
12 |
Correct |
267 ms |
22708 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
249 ms |
18684 KB |
Output is correct |
2 |
Correct |
274 ms |
18420 KB |
Output is correct |
3 |
Correct |
236 ms |
18424 KB |
Output is correct |
4 |
Correct |
256 ms |
18708 KB |
Output is correct |
5 |
Correct |
268 ms |
18420 KB |
Output is correct |
6 |
Correct |
221 ms |
18224 KB |
Output is correct |
7 |
Correct |
245 ms |
22000 KB |
Output is correct |
8 |
Correct |
247 ms |
21904 KB |
Output is correct |
9 |
Correct |
268 ms |
21900 KB |
Output is correct |
10 |
Correct |
255 ms |
21904 KB |
Output is correct |
11 |
Correct |
100 ms |
16188 KB |
Output is correct |
12 |
Correct |
244 ms |
22024 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
1004 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
12 ms |
2388 KB |
Output is correct |
5 |
Correct |
7 ms |
1356 KB |
Output is correct |
6 |
Correct |
1 ms |
328 KB |
Output is correct |
7 |
Correct |
2 ms |
468 KB |
Output is correct |
8 |
Correct |
2 ms |
464 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
6 ms |
1364 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
320 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
241 ms |
19652 KB |
Output is correct |
2 |
Correct |
249 ms |
18560 KB |
Output is correct |
3 |
Correct |
271 ms |
18264 KB |
Output is correct |
4 |
Correct |
258 ms |
22316 KB |
Output is correct |
5 |
Correct |
233 ms |
21804 KB |
Output is correct |
6 |
Correct |
262 ms |
23588 KB |
Output is correct |
7 |
Correct |
244 ms |
22172 KB |
Output is correct |
8 |
Correct |
248 ms |
22136 KB |
Output is correct |
9 |
Correct |
230 ms |
22664 KB |
Output is correct |
10 |
Correct |
215 ms |
22720 KB |
Output is correct |
11 |
Correct |
113 ms |
16048 KB |
Output is correct |
12 |
Correct |
267 ms |
22708 KB |
Output is correct |
13 |
Correct |
249 ms |
18684 KB |
Output is correct |
14 |
Correct |
274 ms |
18420 KB |
Output is correct |
15 |
Correct |
236 ms |
18424 KB |
Output is correct |
16 |
Correct |
256 ms |
18708 KB |
Output is correct |
17 |
Correct |
268 ms |
18420 KB |
Output is correct |
18 |
Correct |
221 ms |
18224 KB |
Output is correct |
19 |
Correct |
245 ms |
22000 KB |
Output is correct |
20 |
Correct |
247 ms |
21904 KB |
Output is correct |
21 |
Correct |
268 ms |
21900 KB |
Output is correct |
22 |
Correct |
255 ms |
21904 KB |
Output is correct |
23 |
Correct |
100 ms |
16188 KB |
Output is correct |
24 |
Correct |
244 ms |
22024 KB |
Output is correct |
25 |
Correct |
10 ms |
1004 KB |
Output is correct |
26 |
Correct |
1 ms |
340 KB |
Output is correct |
27 |
Correct |
1 ms |
340 KB |
Output is correct |
28 |
Correct |
12 ms |
2388 KB |
Output is correct |
29 |
Correct |
7 ms |
1356 KB |
Output is correct |
30 |
Correct |
1 ms |
328 KB |
Output is correct |
31 |
Correct |
2 ms |
468 KB |
Output is correct |
32 |
Correct |
2 ms |
464 KB |
Output is correct |
33 |
Correct |
1 ms |
332 KB |
Output is correct |
34 |
Correct |
6 ms |
1364 KB |
Output is correct |
35 |
Correct |
1 ms |
340 KB |
Output is correct |
36 |
Correct |
1 ms |
320 KB |
Output is correct |
37 |
Correct |
1 ms |
340 KB |
Output is correct |
38 |
Correct |
1 ms |
340 KB |
Output is correct |
39 |
Correct |
1 ms |
340 KB |
Output is correct |
40 |
Correct |
247 ms |
24132 KB |
Output is correct |
41 |
Correct |
244 ms |
22604 KB |
Output is correct |
42 |
Correct |
261 ms |
22732 KB |
Output is correct |
43 |
Correct |
99 ms |
16056 KB |
Output is correct |
44 |
Correct |
99 ms |
16132 KB |
Output is correct |
45 |
Correct |
230 ms |
21524 KB |
Output is correct |
46 |
Correct |
271 ms |
21368 KB |
Output is correct |
47 |
Correct |
236 ms |
22224 KB |
Output is correct |
48 |
Correct |
106 ms |
15548 KB |
Output is correct |
49 |
Correct |
243 ms |
23740 KB |
Output is correct |
50 |
Correct |
218 ms |
21484 KB |
Output is correct |
51 |
Correct |
226 ms |
21808 KB |
Output is correct |