#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);
vector<LL> odl(n, INF);
vector<int> odw(n, 0);
vector<array<LL, 3>> dp(n, array<LL, 3> {INF, INF, 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 &i : v[x]) {
if (odl[i.first] > odl[x] + i.second) {
odl[i.first] = odl[x] + i.second;
pq.push({-odl[i.first], i.first});
dp[i.first] = dp[x];
}
if (odl[i.first] == odl[x] + i.second) {
REP (j, 3) {
dp[i.first][j] = min(dp[i.first][j], dp[x][j]);
}
}
}
}
cout << min(dp[T][2], odlU[V]) << endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
218 ms |
21220 KB |
Output is correct |
2 |
Correct |
216 ms |
19488 KB |
Output is correct |
3 |
Correct |
229 ms |
19352 KB |
Output is correct |
4 |
Correct |
198 ms |
19704 KB |
Output is correct |
5 |
Correct |
213 ms |
19180 KB |
Output is correct |
6 |
Correct |
263 ms |
21192 KB |
Output is correct |
7 |
Correct |
211 ms |
19384 KB |
Output is correct |
8 |
Correct |
238 ms |
19356 KB |
Output is correct |
9 |
Correct |
250 ms |
20156 KB |
Output is correct |
10 |
Correct |
178 ms |
20088 KB |
Output is correct |
11 |
Correct |
99 ms |
12860 KB |
Output is correct |
12 |
Correct |
247 ms |
20076 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
219 ms |
19704 KB |
Output is correct |
2 |
Correct |
255 ms |
19348 KB |
Output is correct |
3 |
Correct |
232 ms |
19324 KB |
Output is correct |
4 |
Correct |
260 ms |
19360 KB |
Output is correct |
5 |
Correct |
217 ms |
19316 KB |
Output is correct |
6 |
Correct |
207 ms |
19376 KB |
Output is correct |
7 |
Correct |
256 ms |
19224 KB |
Output is correct |
8 |
Correct |
259 ms |
19376 KB |
Output is correct |
9 |
Correct |
228 ms |
19292 KB |
Output is correct |
10 |
Correct |
264 ms |
19372 KB |
Output is correct |
11 |
Correct |
96 ms |
12988 KB |
Output is correct |
12 |
Correct |
214 ms |
19316 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
1364 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
13 ms |
2380 KB |
Output is correct |
5 |
Correct |
6 ms |
1364 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
468 KB |
Output is correct |
8 |
Correct |
2 ms |
404 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
6 ms |
1380 KB |
Output is correct |
11 |
Correct |
1 ms |
324 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 |
328 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
218 ms |
21220 KB |
Output is correct |
2 |
Correct |
216 ms |
19488 KB |
Output is correct |
3 |
Correct |
229 ms |
19352 KB |
Output is correct |
4 |
Correct |
198 ms |
19704 KB |
Output is correct |
5 |
Correct |
213 ms |
19180 KB |
Output is correct |
6 |
Correct |
263 ms |
21192 KB |
Output is correct |
7 |
Correct |
211 ms |
19384 KB |
Output is correct |
8 |
Correct |
238 ms |
19356 KB |
Output is correct |
9 |
Correct |
250 ms |
20156 KB |
Output is correct |
10 |
Correct |
178 ms |
20088 KB |
Output is correct |
11 |
Correct |
99 ms |
12860 KB |
Output is correct |
12 |
Correct |
247 ms |
20076 KB |
Output is correct |
13 |
Correct |
219 ms |
19704 KB |
Output is correct |
14 |
Correct |
255 ms |
19348 KB |
Output is correct |
15 |
Correct |
232 ms |
19324 KB |
Output is correct |
16 |
Correct |
260 ms |
19360 KB |
Output is correct |
17 |
Correct |
217 ms |
19316 KB |
Output is correct |
18 |
Correct |
207 ms |
19376 KB |
Output is correct |
19 |
Correct |
256 ms |
19224 KB |
Output is correct |
20 |
Correct |
259 ms |
19376 KB |
Output is correct |
21 |
Correct |
228 ms |
19292 KB |
Output is correct |
22 |
Correct |
264 ms |
19372 KB |
Output is correct |
23 |
Correct |
96 ms |
12988 KB |
Output is correct |
24 |
Correct |
214 ms |
19316 KB |
Output is correct |
25 |
Correct |
12 ms |
1364 KB |
Output is correct |
26 |
Correct |
1 ms |
340 KB |
Output is correct |
27 |
Correct |
1 ms |
340 KB |
Output is correct |
28 |
Correct |
13 ms |
2380 KB |
Output is correct |
29 |
Correct |
6 ms |
1364 KB |
Output is correct |
30 |
Correct |
1 ms |
340 KB |
Output is correct |
31 |
Correct |
1 ms |
468 KB |
Output is correct |
32 |
Correct |
2 ms |
404 KB |
Output is correct |
33 |
Correct |
1 ms |
340 KB |
Output is correct |
34 |
Correct |
6 ms |
1380 KB |
Output is correct |
35 |
Correct |
1 ms |
324 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 |
328 KB |
Output is correct |
40 |
Correct |
211 ms |
21496 KB |
Output is correct |
41 |
Correct |
258 ms |
20048 KB |
Output is correct |
42 |
Correct |
229 ms |
20080 KB |
Output is correct |
43 |
Correct |
79 ms |
13004 KB |
Output is correct |
44 |
Correct |
108 ms |
12876 KB |
Output is correct |
45 |
Correct |
225 ms |
18996 KB |
Output is correct |
46 |
Correct |
181 ms |
18676 KB |
Output is correct |
47 |
Correct |
223 ms |
19632 KB |
Output is correct |
48 |
Correct |
115 ms |
12348 KB |
Output is correct |
49 |
Correct |
178 ms |
20984 KB |
Output is correct |
50 |
Correct |
191 ms |
18900 KB |
Output is correct |
51 |
Correct |
185 ms |
19148 KB |
Output is correct |