#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<int, int> pii;
typedef pair<ld, ld> pld;
const ll inf = 1e18 + 7;
ll n, m;
ll s, t;
ll u, v;
vector<pll> g[100009];
vector<ll> tree[100009];
ll diss[100009];
ll dist[100009];
ll disu[100009];
ll disv[100009];
ll ans;
void dijk(ll beg, ll dis[]){
for(ll i = 1; i <= n; ++i){
dis[i] = inf;
}
dis[beg] = 0;
priority_queue<pll, vector<pll>, greater<pll>> pq;
pq.push({dis[beg], beg});
while(pq.size()){
ll v = pq.top().ss;
ll d = pq.top().ff;
pq.pop();
if(dis[v] < d) continue;
for(auto u : g[v])
if(d+u.ss < dis[u.ff]){
dis[u.ff] = d+u.ss;
pq.push({dis[u.ff], u.ff});
}
}
}
ll vis[100009];
void calctree(ll beg, ll dis[], ll um[], ll vm[], ll bm[], ll addtree){
for(ll i = 1; i <= n; ++i){
um[i] = vm[i] = bm[i] = inf;
vis[i] = 0;
}
vis[beg] = 1;
um[beg] = disu[beg];
vm[beg] = disv[beg];
bm[beg] = um[beg]+vm[beg];
priority_queue<pll, vector<pll>, greater<pll>> pq;
pq.push({dis[beg], beg});
while(pq.size()){
ll v = pq.top().ss;
pq.pop();
for(auto u : g[v]){
if(dis[v]+u.ss != dis[u.ff]) continue;
um[u.ff] = min({disu[u.ff], um[v], um[u.ff]});
vm[u.ff] = min({disv[u.ff], vm[v], vm[u.ff]});
bm[u.ff] = min({disu[u.ff]+vm[u.ff],disv[u.ff]+um[u.ff],bm[v], bm[u.ff]});
if(addtree)
tree[u.ff].pb(v);
if(vis[u.ff] == 0){
vis[u.ff] = 1;
pq.push({dis[u.ff], u.ff});
}
}
}
}
ll um1[100009], vm1[100009], bm1[100009];
ll um2[100009], vm2[100009], bm2[100009];
ll clear[100009];
void dfs(ll v){
clear[v] = 1;
for(auto u : tree[v])
if(!clear[u])
dfs(u);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
cin >> n >> m;
cin >> s >> t;
cin >> u >> v;
while(m--){
ll x, y, z;
cin >> x >> y >> z;
g[x].pb({y, z});
g[y].pb({x, z});
}
ll empty[1];
dijk(u, disu);
dijk(v, disv);
dijk(s, diss);
calctree(s, diss, um1, vm1, bm1, 0);
dijk(t, dist);
calctree(t, dist, um2, vm2, bm2, 1);
dfs(s);
ans = disu[v];
for(ll i = 1; i <= n; ++i){
if(clear[i] == 0) continue;
ans = min({ans, bm1[i], bm2[i], vm1[i]+um2[i], um1[i]+vm2[i]});
}
cout << ans;
}
Compilation message
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:98:8: warning: unused variable 'empty' [-Wunused-variable]
ll empty[1];
^~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
532 ms |
27152 KB |
Output is correct |
2 |
Correct |
493 ms |
27660 KB |
Output is correct |
3 |
Correct |
451 ms |
30020 KB |
Output is correct |
4 |
Correct |
505 ms |
27520 KB |
Output is correct |
5 |
Correct |
642 ms |
27664 KB |
Output is correct |
6 |
Correct |
640 ms |
27252 KB |
Output is correct |
7 |
Correct |
479 ms |
27632 KB |
Output is correct |
8 |
Correct |
479 ms |
27808 KB |
Output is correct |
9 |
Correct |
537 ms |
27276 KB |
Output is correct |
10 |
Correct |
410 ms |
27332 KB |
Output is correct |
11 |
Correct |
316 ms |
24056 KB |
Output is correct |
12 |
Correct |
641 ms |
26844 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
503 ms |
28516 KB |
Output is correct |
2 |
Correct |
504 ms |
28396 KB |
Output is correct |
3 |
Correct |
625 ms |
28312 KB |
Output is correct |
4 |
Correct |
541 ms |
28276 KB |
Output is correct |
5 |
Correct |
446 ms |
28532 KB |
Output is correct |
6 |
Correct |
491 ms |
29760 KB |
Output is correct |
7 |
Correct |
571 ms |
29420 KB |
Output is correct |
8 |
Correct |
636 ms |
28388 KB |
Output is correct |
9 |
Correct |
517 ms |
28644 KB |
Output is correct |
10 |
Correct |
518 ms |
28268 KB |
Output is correct |
11 |
Correct |
235 ms |
24568 KB |
Output is correct |
12 |
Correct |
479 ms |
29760 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
6528 KB |
Output is correct |
2 |
Correct |
4 ms |
5120 KB |
Output is correct |
3 |
Correct |
4 ms |
5120 KB |
Output is correct |
4 |
Correct |
23 ms |
8056 KB |
Output is correct |
5 |
Correct |
11 ms |
6528 KB |
Output is correct |
6 |
Correct |
5 ms |
5248 KB |
Output is correct |
7 |
Correct |
5 ms |
5248 KB |
Output is correct |
8 |
Correct |
6 ms |
5376 KB |
Output is correct |
9 |
Correct |
4 ms |
5248 KB |
Output is correct |
10 |
Correct |
14 ms |
6784 KB |
Output is correct |
11 |
Correct |
4 ms |
5120 KB |
Output is correct |
12 |
Correct |
4 ms |
5120 KB |
Output is correct |
13 |
Correct |
4 ms |
5120 KB |
Output is correct |
14 |
Correct |
5 ms |
5248 KB |
Output is correct |
15 |
Correct |
6 ms |
5248 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
532 ms |
27152 KB |
Output is correct |
2 |
Correct |
493 ms |
27660 KB |
Output is correct |
3 |
Correct |
451 ms |
30020 KB |
Output is correct |
4 |
Correct |
505 ms |
27520 KB |
Output is correct |
5 |
Correct |
642 ms |
27664 KB |
Output is correct |
6 |
Correct |
640 ms |
27252 KB |
Output is correct |
7 |
Correct |
479 ms |
27632 KB |
Output is correct |
8 |
Correct |
479 ms |
27808 KB |
Output is correct |
9 |
Correct |
537 ms |
27276 KB |
Output is correct |
10 |
Correct |
410 ms |
27332 KB |
Output is correct |
11 |
Correct |
316 ms |
24056 KB |
Output is correct |
12 |
Correct |
641 ms |
26844 KB |
Output is correct |
13 |
Correct |
503 ms |
28516 KB |
Output is correct |
14 |
Correct |
504 ms |
28396 KB |
Output is correct |
15 |
Correct |
625 ms |
28312 KB |
Output is correct |
16 |
Correct |
541 ms |
28276 KB |
Output is correct |
17 |
Correct |
446 ms |
28532 KB |
Output is correct |
18 |
Correct |
491 ms |
29760 KB |
Output is correct |
19 |
Correct |
571 ms |
29420 KB |
Output is correct |
20 |
Correct |
636 ms |
28388 KB |
Output is correct |
21 |
Correct |
517 ms |
28644 KB |
Output is correct |
22 |
Correct |
518 ms |
28268 KB |
Output is correct |
23 |
Correct |
235 ms |
24568 KB |
Output is correct |
24 |
Correct |
479 ms |
29760 KB |
Output is correct |
25 |
Correct |
14 ms |
6528 KB |
Output is correct |
26 |
Correct |
4 ms |
5120 KB |
Output is correct |
27 |
Correct |
4 ms |
5120 KB |
Output is correct |
28 |
Correct |
23 ms |
8056 KB |
Output is correct |
29 |
Correct |
11 ms |
6528 KB |
Output is correct |
30 |
Correct |
5 ms |
5248 KB |
Output is correct |
31 |
Correct |
5 ms |
5248 KB |
Output is correct |
32 |
Correct |
6 ms |
5376 KB |
Output is correct |
33 |
Correct |
4 ms |
5248 KB |
Output is correct |
34 |
Correct |
14 ms |
6784 KB |
Output is correct |
35 |
Correct |
4 ms |
5120 KB |
Output is correct |
36 |
Correct |
4 ms |
5120 KB |
Output is correct |
37 |
Correct |
4 ms |
5120 KB |
Output is correct |
38 |
Correct |
5 ms |
5248 KB |
Output is correct |
39 |
Correct |
6 ms |
5248 KB |
Output is correct |
40 |
Correct |
564 ms |
31112 KB |
Output is correct |
41 |
Correct |
519 ms |
31256 KB |
Output is correct |
42 |
Correct |
472 ms |
31256 KB |
Output is correct |
43 |
Correct |
229 ms |
26156 KB |
Output is correct |
44 |
Correct |
242 ms |
26232 KB |
Output is correct |
45 |
Correct |
480 ms |
31888 KB |
Output is correct |
46 |
Correct |
475 ms |
31512 KB |
Output is correct |
47 |
Correct |
505 ms |
31260 KB |
Output is correct |
48 |
Correct |
248 ms |
24824 KB |
Output is correct |
49 |
Correct |
433 ms |
32416 KB |
Output is correct |
50 |
Correct |
485 ms |
31588 KB |
Output is correct |
51 |
Correct |
456 ms |
31764 KB |
Output is correct |