/*---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---*/
#include "bits/stdc++.h"
using namespace std;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define dbg(x...)
#endif
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define rrep(a, b, c) for(int a = (b); a > c; --a)
#define each(a, b) for(auto& a : b)
#define sz(x) (int)(x).size()
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define vi vector<int>
#define ar array
template<class T> using V = vector<T>;
template<class T> using pq = priority_queue<T>;
template<class T> using pqg = priority_queue<T, vector<T>, greater<T>>;
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define eb emplace_back
#define rsz resize
#define bk back()
#define pi pair<int, int>
#define pl pair<ll, ll>
#define mp make_pair
#define f first
#define s second
#define pct(x) __builtin_popcount(x)
constexpr int fsb(int x) {return __builtin_ffs(x) - 1;} // first set bit
constexpr int log2(int x) {return x == 0 ? 0 : 31-__builtin_clz(x);} // floor(log2(x))
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
template <class T> bool umin(T& a, const T& b){return b<a?a=b, 1:0;}
template <class T> bool umax(T& a, const T& b){return a<b?a=b, 1:0;}
const int d4i[4]={-1, 0, 1, 0}, d4j[4]={0, 1, 0, -1};
const int d8i[8]={-1, -1, 0, 1, 1, 1, 0, -1}, d8j[8]={0, 1, 1, 1, 0, -1, -1, -1};
using ll = long long;
using ld = long double;
using str = string;
const int inf = (int)1e9 + 5;
const ll infl = (ll)1e18 + 5;
const ld PI = acos((ld)-1);
const int MOD = 1e9 + 7;
const int N = 1e5 + 10;
/*---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---*/
#define int ll
int n, m, s, t, u, v;
V<V<pi>> g(N);
V<vi> ad(N);
void solve(){
cin >> n >> m >> s >> t >> u >> v;
--s; --t; --u; --v;
rep(i, 0, m){
int a, b, c; cin >> a >> b >> c;
g[--a].eb(--b, c);
g[b].eb(a, c);
}
// DIJkstra
pqg <pl> pq;
V<ll> d(n, infl);
V<vi> p(n);
pq.emplace(d[s] = 0, s);
V<bool> vis(n);
while(!pq.empty()){
auto [od, x] = pq.top(); pq.pop();
if(d[x] != od) continue;
for(auto [y, e] : g[x]){
if(umin(d[y], od + e)){
p[y].clear();
pq.emplace(d[y], y);
}
if(d[y] == od + e){
p[y].eb(x);
}
}
}
function<void(int)> dfs = [&](int s){
vis[s] = 1;
each(x, p[s]) if(!vis[x]){
dfs(x);
}
};
dfs(t);
rep(i, 0, n){
if(!vis[i]){
p[i].clear(); continue;
}
rep(j, 0, sz(p[i])){
auto &x = p[i][j];
if(!vis[x]){
swap(x, p[i].bk);
p[i].pop_back(); --j;
}
}
}
rep(i, 0, n) if(vis[i]){
each(x, p[i]){
ad[x].eb(i);
}
}
d = V<ll> (4*n, infl);
pq.emplace(d[u] = 0, u);
while(!pq.empty()){
auto [od, x] = pq.top(); pq.pop();
if(d[x] != od) continue;
int zx = x;
while(x >= n) x -= n;
if(zx < 2*n){
for(auto y : ad[x]){
if(umin(d[y += n], od)){
pq.emplace(d[y], y);
}
}
}
if((zx < n || zx >= 2*n) && zx < 3*n){
for(auto y : p[x]){
if(umin(d[y += 2*n], od)){
pq.emplace(d[y], y);
}
}
}
for(auto [y, e] : g[x]){
if(zx >= n) y += 3*n;
if(umin(d[y], od + e)){
pq.emplace(d[y], y);
}
}
}
cout << min({d[v], d[v+n], d[v+2*n], d[v+3*n]}) << '\n';
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
256 ms |
27592 KB |
Output is correct |
2 |
Correct |
299 ms |
26624 KB |
Output is correct |
3 |
Correct |
356 ms |
33876 KB |
Output is correct |
4 |
Correct |
252 ms |
25888 KB |
Output is correct |
5 |
Correct |
353 ms |
29540 KB |
Output is correct |
6 |
Correct |
245 ms |
27624 KB |
Output is correct |
7 |
Correct |
357 ms |
29816 KB |
Output is correct |
8 |
Correct |
337 ms |
29444 KB |
Output is correct |
9 |
Correct |
279 ms |
25636 KB |
Output is correct |
10 |
Correct |
232 ms |
25540 KB |
Output is correct |
11 |
Correct |
158 ms |
24764 KB |
Output is correct |
12 |
Correct |
263 ms |
25640 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
313 ms |
28136 KB |
Output is correct |
2 |
Correct |
337 ms |
28660 KB |
Output is correct |
3 |
Correct |
322 ms |
30100 KB |
Output is correct |
4 |
Correct |
316 ms |
28520 KB |
Output is correct |
5 |
Correct |
361 ms |
29092 KB |
Output is correct |
6 |
Correct |
342 ms |
33320 KB |
Output is correct |
7 |
Correct |
385 ms |
34008 KB |
Output is correct |
8 |
Correct |
331 ms |
28572 KB |
Output is correct |
9 |
Correct |
333 ms |
29200 KB |
Output is correct |
10 |
Correct |
322 ms |
28220 KB |
Output is correct |
11 |
Correct |
218 ms |
27760 KB |
Output is correct |
12 |
Correct |
351 ms |
33664 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
6760 KB |
Output is correct |
2 |
Correct |
3 ms |
5076 KB |
Output is correct |
3 |
Correct |
3 ms |
5044 KB |
Output is correct |
4 |
Correct |
20 ms |
8532 KB |
Output is correct |
5 |
Correct |
10 ms |
6740 KB |
Output is correct |
6 |
Correct |
3 ms |
5076 KB |
Output is correct |
7 |
Correct |
4 ms |
5204 KB |
Output is correct |
8 |
Correct |
4 ms |
5204 KB |
Output is correct |
9 |
Correct |
4 ms |
5076 KB |
Output is correct |
10 |
Correct |
9 ms |
6840 KB |
Output is correct |
11 |
Correct |
3 ms |
5076 KB |
Output is correct |
12 |
Correct |
3 ms |
5076 KB |
Output is correct |
13 |
Correct |
3 ms |
5076 KB |
Output is correct |
14 |
Correct |
3 ms |
5048 KB |
Output is correct |
15 |
Correct |
3 ms |
5040 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
256 ms |
27592 KB |
Output is correct |
2 |
Correct |
299 ms |
26624 KB |
Output is correct |
3 |
Correct |
356 ms |
33876 KB |
Output is correct |
4 |
Correct |
252 ms |
25888 KB |
Output is correct |
5 |
Correct |
353 ms |
29540 KB |
Output is correct |
6 |
Correct |
245 ms |
27624 KB |
Output is correct |
7 |
Correct |
357 ms |
29816 KB |
Output is correct |
8 |
Correct |
337 ms |
29444 KB |
Output is correct |
9 |
Correct |
279 ms |
25636 KB |
Output is correct |
10 |
Correct |
232 ms |
25540 KB |
Output is correct |
11 |
Correct |
158 ms |
24764 KB |
Output is correct |
12 |
Correct |
263 ms |
25640 KB |
Output is correct |
13 |
Correct |
313 ms |
28136 KB |
Output is correct |
14 |
Correct |
337 ms |
28660 KB |
Output is correct |
15 |
Correct |
322 ms |
30100 KB |
Output is correct |
16 |
Correct |
316 ms |
28520 KB |
Output is correct |
17 |
Correct |
361 ms |
29092 KB |
Output is correct |
18 |
Correct |
342 ms |
33320 KB |
Output is correct |
19 |
Correct |
385 ms |
34008 KB |
Output is correct |
20 |
Correct |
331 ms |
28572 KB |
Output is correct |
21 |
Correct |
333 ms |
29200 KB |
Output is correct |
22 |
Correct |
322 ms |
28220 KB |
Output is correct |
23 |
Correct |
218 ms |
27760 KB |
Output is correct |
24 |
Correct |
351 ms |
33664 KB |
Output is correct |
25 |
Correct |
10 ms |
6760 KB |
Output is correct |
26 |
Correct |
3 ms |
5076 KB |
Output is correct |
27 |
Correct |
3 ms |
5044 KB |
Output is correct |
28 |
Correct |
20 ms |
8532 KB |
Output is correct |
29 |
Correct |
10 ms |
6740 KB |
Output is correct |
30 |
Correct |
3 ms |
5076 KB |
Output is correct |
31 |
Correct |
4 ms |
5204 KB |
Output is correct |
32 |
Correct |
4 ms |
5204 KB |
Output is correct |
33 |
Correct |
4 ms |
5076 KB |
Output is correct |
34 |
Correct |
9 ms |
6840 KB |
Output is correct |
35 |
Correct |
3 ms |
5076 KB |
Output is correct |
36 |
Correct |
3 ms |
5076 KB |
Output is correct |
37 |
Correct |
3 ms |
5076 KB |
Output is correct |
38 |
Correct |
3 ms |
5048 KB |
Output is correct |
39 |
Correct |
3 ms |
5040 KB |
Output is correct |
40 |
Correct |
236 ms |
31620 KB |
Output is correct |
41 |
Correct |
271 ms |
29084 KB |
Output is correct |
42 |
Correct |
254 ms |
29092 KB |
Output is correct |
43 |
Correct |
222 ms |
29944 KB |
Output is correct |
44 |
Correct |
210 ms |
29972 KB |
Output is correct |
45 |
Correct |
417 ms |
35116 KB |
Output is correct |
46 |
Correct |
430 ms |
34864 KB |
Output is correct |
47 |
Correct |
259 ms |
29784 KB |
Output is correct |
48 |
Correct |
243 ms |
27192 KB |
Output is correct |
49 |
Correct |
232 ms |
32328 KB |
Output is correct |
50 |
Correct |
376 ms |
34236 KB |
Output is correct |
51 |
Correct |
416 ms |
34988 KB |
Output is correct |