#include <bits/stdc++.h>
#include <fstream>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template<class A, class B>
ostream& operator<<(ostream& o, const pair<A, B>& p) {return o << '(' << p.first << ", " << p.second << ')';}
template<size_t Index = 0, typename... Types>
ostream& printTupleElements(ostream& o, const tuple<Types...>& t) {if constexpr (Index < sizeof...(Types)){if(Index > 0){o << ", ";}o << get<Index>(t);printTupleElements<Index + 1>(o, t);}return o;}
template<typename... Types>
ostream& operator<<(ostream& o, const tuple<Types...>& t){o << "(";printTupleElements(o, t);return o << ")";}
template<class T>
auto operator<<(ostream& o, const T& x) -> decltype(x.end(), o){o << '{';bool first = true;for (const auto& e : x){if (!first){o << ", ";}o << e;first = false;} return o << '}';}
//#define DEBUG
#ifdef DEBUG
#define fastio()
#define debug(x...) cerr << "[" #x "]: ", [](auto... $) {((cerr << $ << "; "), ...); }(x), cerr << '\n'
#define check(x) if (!(x)) { cerr << "Check failed: " << #x << " in line " << __LINE__ << endl; exit(1); }
#else
#define fastio() ios_base::sync_with_stdio(0); cin.tie(0);
#define debug(...)
#define check(x)
#endif
typedef long long ll;
#define pi pair<int, int>
#define pl pair<ll, ll>
#define st first
#define nd second
#define vi vector<int>
#define vll vector<ll>
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
constexpr int LIM = 1e5;
constexpr ll INF = 1e18;
struct res{
pl minsum = make_pair(INF, INF);
pl minA = make_pair(INF, INF);
pl minB = make_pair(INF, INF);
};
gp_hash_table<int, ll>dist[LIM + 10];
res ans[LIM + 10];
vector<pi>g[LIM + 10];
void dji(int s, int n) {
for(int i = 1; i <= n; i++) {
dist[s][i] = INF;
}
dist[s][s] = 0;
priority_queue<pair<ll, int> >q;
q.emplace(0, s);
while(!q.empty()) {
int v = q.top().nd;
ll d = -q.top().st;
q.pop();
if(dist[s][v] == d) {
for(auto &[u, val] : g[v]) {
if(dist[s][u] > dist[s][v] + val) {
dist[s][u] = dist[s][v] + val;
q.emplace(-dist[s][u], u);
}
}
}
}
}
int U, V;
void cntres(int s, int n) {
for(int i = 1; i <= n; i++) {
dist[s][i] = INF;
}
dist[s][s] = 0;
pl tmp = make_pair(dist[V][s], dist[U][s]);
ans[s].minsum = tmp;
ans[s].minA = tmp;
ans[s].minB = tmp;
priority_queue<pair<ll, int> >q;
q.emplace(0, s);
while(!q.empty()) {
int v = q.top().nd;
ll d = -q.top().st;
q.pop();
if(dist[s][v] == d) {
for(auto &[u, val] : g[v]) {
if(dist[s][u] > dist[s][v] + val) {
pl par1 = make_pair(min(ans[v].minsum.st, dist[V][u]), min(ans[v].minsum.nd, dist[U][u]));
pl par2 = make_pair(min(ans[v].minA.st, dist[V][u]), min(ans[v].minA.nd, dist[U][u]));
pl par3 = make_pair(min(ans[v].minB.st, dist[V][u]), min(ans[v].minB.nd, dist[U][u]));
ans[u].minA = par2;
ans[u].minB = par3;
ans[u].minsum = make_pair(INF, INF);
if(ans[u].minsum.st + ans[u].minsum.nd > par1.st + par1.nd) {
ans[u].minsum = par1;
}
if(ans[u].minsum.st + ans[u].minsum.nd > par2.st + par2.nd) {
ans[u].minsum = par2;
}
if(ans[u].minsum.st + ans[u].minsum.nd > par3.st + par3.nd) {
ans[u].minsum = par3;
}
}
else if(dist[s][u] == dist[s][v] + val) {
debug(v, u);
pl par1 = make_pair(min(ans[v].minsum.st, dist[V][u]), min(ans[v].minsum.nd, dist[U][u]));
pl par2 = make_pair(min(ans[v].minA.st, dist[V][u]), min(ans[v].minA.nd, dist[U][u]));
pl par3 = make_pair(min(ans[v].minB.st, dist[V][u]), min(ans[v].minB.nd, dist[U][u]));
if(ans[u].minsum.st + ans[u].minsum.nd > par1.st + par1.nd) {
ans[u].minsum = par1;
}
if(ans[u].minsum.st + ans[u].minsum.nd > par2.st + par2.nd) {
ans[u].minsum = par2;
}
if(ans[u].minsum.st + ans[u].minsum.nd > par3.st + par3.nd) {
ans[u].minsum = par3;
}
if(ans[u].minA.st > par2.st) {
ans[u].minA = par2;
}
if(ans[u].minB.nd > par3.nd) {
ans[u].minB = par3;
}
}
if(dist[s][u] > dist[s][v] + val) {
dist[s][u] = dist[s][v] + val;
q.emplace(-dist[s][u], u);
}
}
}
}
}
void solve() {
//ifstream cin("nazwa.in");
//ofstream cout("nazwa.out");
int n, m;
cin >> n >> m;
int s, t;
cin >> s >> t;
cin >> V >> U;
for(int i = 1; i <= m; i++) {
int a, b, x;
cin >> a >> b >> x;
g[a].eb(b, x);
g[b].eb(a, x);
}
dji(U, n);
dji(V, n);
for(int i = 1; i <= n; i++) {
//debug(i, dist[U][i], dist[V][i]);
}
cntres(s, n);
for(int i = 1; i <= n; i++) {
//debug(i, ans[i].minsum, ans[i].minA, ans[i].minB);
}
cout << min(dist[V][U], ans[t].minsum.st + ans[t].minsum.nd) << '\n';
}
int main() {
fastio();
int t = 1;
//cin >> t;
while(t--) {
solve();
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
236 ms |
59948 KB |
Output is correct |
2 |
Correct |
241 ms |
58824 KB |
Output is correct |
3 |
Correct |
243 ms |
58220 KB |
Output is correct |
4 |
Correct |
218 ms |
62164 KB |
Output is correct |
5 |
Correct |
238 ms |
63288 KB |
Output is correct |
6 |
Correct |
234 ms |
63528 KB |
Output is correct |
7 |
Correct |
234 ms |
61736 KB |
Output is correct |
8 |
Correct |
238 ms |
61996 KB |
Output is correct |
9 |
Correct |
230 ms |
62760 KB |
Output is correct |
10 |
Correct |
209 ms |
62500 KB |
Output is correct |
11 |
Correct |
122 ms |
58380 KB |
Output is correct |
12 |
Correct |
251 ms |
63700 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
265 ms |
64752 KB |
Output is correct |
2 |
Correct |
266 ms |
64440 KB |
Output is correct |
3 |
Correct |
266 ms |
65956 KB |
Output is correct |
4 |
Correct |
249 ms |
64484 KB |
Output is correct |
5 |
Correct |
249 ms |
64496 KB |
Output is correct |
6 |
Correct |
238 ms |
64304 KB |
Output is correct |
7 |
Correct |
311 ms |
69072 KB |
Output is correct |
8 |
Correct |
258 ms |
69284 KB |
Output is correct |
9 |
Correct |
288 ms |
68084 KB |
Output is correct |
10 |
Correct |
291 ms |
69296 KB |
Output is correct |
11 |
Correct |
127 ms |
63132 KB |
Output is correct |
12 |
Correct |
253 ms |
69540 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
33952 KB |
Output is correct |
2 |
Correct |
19 ms |
33368 KB |
Output is correct |
3 |
Correct |
27 ms |
33368 KB |
Output is correct |
4 |
Correct |
34 ms |
35408 KB |
Output is correct |
5 |
Correct |
24 ms |
34396 KB |
Output is correct |
6 |
Correct |
19 ms |
33372 KB |
Output is correct |
7 |
Correct |
21 ms |
33368 KB |
Output is correct |
8 |
Correct |
21 ms |
33372 KB |
Output is correct |
9 |
Correct |
22 ms |
33468 KB |
Output is correct |
10 |
Correct |
25 ms |
34392 KB |
Output is correct |
11 |
Correct |
20 ms |
33344 KB |
Output is correct |
12 |
Correct |
20 ms |
33368 KB |
Output is correct |
13 |
Correct |
21 ms |
33372 KB |
Output is correct |
14 |
Correct |
18 ms |
33372 KB |
Output is correct |
15 |
Correct |
21 ms |
33596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
236 ms |
59948 KB |
Output is correct |
2 |
Correct |
241 ms |
58824 KB |
Output is correct |
3 |
Correct |
243 ms |
58220 KB |
Output is correct |
4 |
Correct |
218 ms |
62164 KB |
Output is correct |
5 |
Correct |
238 ms |
63288 KB |
Output is correct |
6 |
Correct |
234 ms |
63528 KB |
Output is correct |
7 |
Correct |
234 ms |
61736 KB |
Output is correct |
8 |
Correct |
238 ms |
61996 KB |
Output is correct |
9 |
Correct |
230 ms |
62760 KB |
Output is correct |
10 |
Correct |
209 ms |
62500 KB |
Output is correct |
11 |
Correct |
122 ms |
58380 KB |
Output is correct |
12 |
Correct |
251 ms |
63700 KB |
Output is correct |
13 |
Correct |
265 ms |
64752 KB |
Output is correct |
14 |
Correct |
266 ms |
64440 KB |
Output is correct |
15 |
Correct |
266 ms |
65956 KB |
Output is correct |
16 |
Correct |
249 ms |
64484 KB |
Output is correct |
17 |
Correct |
249 ms |
64496 KB |
Output is correct |
18 |
Correct |
238 ms |
64304 KB |
Output is correct |
19 |
Correct |
311 ms |
69072 KB |
Output is correct |
20 |
Correct |
258 ms |
69284 KB |
Output is correct |
21 |
Correct |
288 ms |
68084 KB |
Output is correct |
22 |
Correct |
291 ms |
69296 KB |
Output is correct |
23 |
Correct |
127 ms |
63132 KB |
Output is correct |
24 |
Correct |
253 ms |
69540 KB |
Output is correct |
25 |
Correct |
25 ms |
33952 KB |
Output is correct |
26 |
Correct |
19 ms |
33368 KB |
Output is correct |
27 |
Correct |
27 ms |
33368 KB |
Output is correct |
28 |
Correct |
34 ms |
35408 KB |
Output is correct |
29 |
Correct |
24 ms |
34396 KB |
Output is correct |
30 |
Correct |
19 ms |
33372 KB |
Output is correct |
31 |
Correct |
21 ms |
33368 KB |
Output is correct |
32 |
Correct |
21 ms |
33372 KB |
Output is correct |
33 |
Correct |
22 ms |
33468 KB |
Output is correct |
34 |
Correct |
25 ms |
34392 KB |
Output is correct |
35 |
Correct |
20 ms |
33344 KB |
Output is correct |
36 |
Correct |
20 ms |
33368 KB |
Output is correct |
37 |
Correct |
21 ms |
33372 KB |
Output is correct |
38 |
Correct |
18 ms |
33372 KB |
Output is correct |
39 |
Correct |
21 ms |
33596 KB |
Output is correct |
40 |
Correct |
252 ms |
70028 KB |
Output is correct |
41 |
Correct |
250 ms |
69796 KB |
Output is correct |
42 |
Correct |
260 ms |
68856 KB |
Output is correct |
43 |
Correct |
126 ms |
63104 KB |
Output is correct |
44 |
Correct |
128 ms |
63048 KB |
Output is correct |
45 |
Correct |
316 ms |
69008 KB |
Output is correct |
46 |
Correct |
272 ms |
67476 KB |
Output is correct |
47 |
Correct |
258 ms |
69392 KB |
Output is correct |
48 |
Correct |
133 ms |
62524 KB |
Output is correct |
49 |
Correct |
277 ms |
70052 KB |
Output is correct |
50 |
Correct |
239 ms |
67712 KB |
Output is correct |
51 |
Correct |
225 ms |
67588 KB |
Output is correct |