#include <bits/stdc++.h>
using namespace std;
#define int long long
#define in ({int x=0;int c=getchar(),n=0;for(;!isdigit(c);c=getchar()) n=(c=='-');for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;})
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r){return l+rng()%(r-l+1);}
#define fasty ios_base::sync_with_stdio(0),cin.tie(0);
#define forinc(a,b,c) for(int a=b,_c=c;a<=_c;++a)
#define fordec(a,b,c) for(int a=b,_c=c;a>=_c;--a)
#define forv(a,b) for(auto&a:b)
#define fi first
#define se second
#define pb push_back
#define ii pair<int,int>
#define mt make_tuple
#define all(a) a.begin(),a.end()
#define reset(f, x) memset(f, x, sizeof(f))
#define bit(x,i) ((x>>(i-1))&1)
#define on(x,i) (x|(1ll<<(i-1)))
#define off(x,i) (x&~(1<<(i-1)))
#define gg exit(0);
const int N=100010,
INF=1e15;
int n,m,s,t,u,v;
int len[N];
vector<ii> ad[N];
void dij(int fw,vector<int>&f){
fill(all(f),INF);
priority_queue<ii,vector<ii>,greater<ii>> q;
q.push({0,fw}); f[fw]=len[fw]=0;
while(q.size()){
int w,u; tie(w,u)=q.top(); q.pop();
forv(v,ad[u]){
if(f[v.fi]>w+v.se){
f[v.fi]=w+v.se;
len[v.fi]=len[u]+1;
q.push({w+v.se,v.fi});
}
}
}
}
main(){
#define task "pass"
//freopen(task".inp","r",stdin);
//freopen(task".out","w",stdout);
n=in,m=in,s=in,t=in,u=in,v=in;
forinc(i,1,m){
int x=in,y=in,w=in;
ad[x].push_back({y,w});
ad[y].push_back({x,w});
}
vector<int> fs(n+1),ft(n+1),fu(n+1),fv(n+1);
dij(t,ft);
dij(u,fu);
dij(v,fv);
dij(s,fs);
int ret=fu[v];
forinc(w,0,1){
vector<int> f(n+1,INF), pf(n+1,INF);
priority_queue<ii,vector<ii>,greater<ii>> q; q.push({0,s}); f[s]=0; pf[s]=fu[s];
while(q.size()){
int w,u; tie(w,u)=q.top(); q.pop();
ret=min(ret,pf[u] + fv[u]);
forv(v,ad[u]){
if(fs[v.fi] + ft[v.fi] == fs[t]){
pf[v.fi]=min({pf[v.fi],fu[v.fi],pf[u]});
if(f[v.fi]>w+v.se){
f[v.fi]=w+v.se;
q.push({w+v.se,v.fi});
}
}
}
}
swap(fv,fu);
}
cout<<ret;
}
Compilation message
commuter_pass.cpp:46:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main(){
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
331 ms |
20276 KB |
Output is correct |
2 |
Correct |
403 ms |
19020 KB |
Output is correct |
3 |
Correct |
428 ms |
19580 KB |
Output is correct |
4 |
Correct |
309 ms |
20020 KB |
Output is correct |
5 |
Correct |
364 ms |
18972 KB |
Output is correct |
6 |
Correct |
351 ms |
20252 KB |
Output is correct |
7 |
Correct |
411 ms |
19072 KB |
Output is correct |
8 |
Correct |
397 ms |
19092 KB |
Output is correct |
9 |
Correct |
331 ms |
18940 KB |
Output is correct |
10 |
Correct |
277 ms |
18672 KB |
Output is correct |
11 |
Correct |
172 ms |
13400 KB |
Output is correct |
12 |
Correct |
391 ms |
18944 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
401 ms |
19132 KB |
Output is correct |
2 |
Correct |
473 ms |
19100 KB |
Output is correct |
3 |
Correct |
423 ms |
19072 KB |
Output is correct |
4 |
Correct |
485 ms |
18948 KB |
Output is correct |
5 |
Correct |
443 ms |
19236 KB |
Output is correct |
6 |
Correct |
424 ms |
19284 KB |
Output is correct |
7 |
Correct |
496 ms |
19480 KB |
Output is correct |
8 |
Correct |
466 ms |
19048 KB |
Output is correct |
9 |
Correct |
445 ms |
19308 KB |
Output is correct |
10 |
Correct |
469 ms |
18956 KB |
Output is correct |
11 |
Correct |
159 ms |
13400 KB |
Output is correct |
12 |
Correct |
467 ms |
19376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
3968 KB |
Output is correct |
2 |
Correct |
7 ms |
2688 KB |
Output is correct |
3 |
Correct |
6 ms |
2688 KB |
Output is correct |
4 |
Correct |
17 ms |
5248 KB |
Output is correct |
5 |
Correct |
12 ms |
3968 KB |
Output is correct |
6 |
Correct |
6 ms |
2816 KB |
Output is correct |
7 |
Correct |
7 ms |
2816 KB |
Output is correct |
8 |
Correct |
7 ms |
2816 KB |
Output is correct |
9 |
Correct |
7 ms |
2816 KB |
Output is correct |
10 |
Correct |
13 ms |
3968 KB |
Output is correct |
11 |
Correct |
6 ms |
2688 KB |
Output is correct |
12 |
Correct |
6 ms |
2688 KB |
Output is correct |
13 |
Correct |
6 ms |
2688 KB |
Output is correct |
14 |
Correct |
6 ms |
2688 KB |
Output is correct |
15 |
Correct |
6 ms |
2688 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
331 ms |
20276 KB |
Output is correct |
2 |
Correct |
403 ms |
19020 KB |
Output is correct |
3 |
Correct |
428 ms |
19580 KB |
Output is correct |
4 |
Correct |
309 ms |
20020 KB |
Output is correct |
5 |
Correct |
364 ms |
18972 KB |
Output is correct |
6 |
Correct |
351 ms |
20252 KB |
Output is correct |
7 |
Correct |
411 ms |
19072 KB |
Output is correct |
8 |
Correct |
397 ms |
19092 KB |
Output is correct |
9 |
Correct |
331 ms |
18940 KB |
Output is correct |
10 |
Correct |
277 ms |
18672 KB |
Output is correct |
11 |
Correct |
172 ms |
13400 KB |
Output is correct |
12 |
Correct |
391 ms |
18944 KB |
Output is correct |
13 |
Correct |
401 ms |
19132 KB |
Output is correct |
14 |
Correct |
473 ms |
19100 KB |
Output is correct |
15 |
Correct |
423 ms |
19072 KB |
Output is correct |
16 |
Correct |
485 ms |
18948 KB |
Output is correct |
17 |
Correct |
443 ms |
19236 KB |
Output is correct |
18 |
Correct |
424 ms |
19284 KB |
Output is correct |
19 |
Correct |
496 ms |
19480 KB |
Output is correct |
20 |
Correct |
466 ms |
19048 KB |
Output is correct |
21 |
Correct |
445 ms |
19308 KB |
Output is correct |
22 |
Correct |
469 ms |
18956 KB |
Output is correct |
23 |
Correct |
159 ms |
13400 KB |
Output is correct |
24 |
Correct |
467 ms |
19376 KB |
Output is correct |
25 |
Correct |
15 ms |
3968 KB |
Output is correct |
26 |
Correct |
7 ms |
2688 KB |
Output is correct |
27 |
Correct |
6 ms |
2688 KB |
Output is correct |
28 |
Correct |
17 ms |
5248 KB |
Output is correct |
29 |
Correct |
12 ms |
3968 KB |
Output is correct |
30 |
Correct |
6 ms |
2816 KB |
Output is correct |
31 |
Correct |
7 ms |
2816 KB |
Output is correct |
32 |
Correct |
7 ms |
2816 KB |
Output is correct |
33 |
Correct |
7 ms |
2816 KB |
Output is correct |
34 |
Correct |
13 ms |
3968 KB |
Output is correct |
35 |
Correct |
6 ms |
2688 KB |
Output is correct |
36 |
Correct |
6 ms |
2688 KB |
Output is correct |
37 |
Correct |
6 ms |
2688 KB |
Output is correct |
38 |
Correct |
6 ms |
2688 KB |
Output is correct |
39 |
Correct |
6 ms |
2688 KB |
Output is correct |
40 |
Correct |
326 ms |
19716 KB |
Output is correct |
41 |
Correct |
352 ms |
19096 KB |
Output is correct |
42 |
Correct |
377 ms |
19020 KB |
Output is correct |
43 |
Correct |
210 ms |
13432 KB |
Output is correct |
44 |
Correct |
180 ms |
15484 KB |
Output is correct |
45 |
Correct |
433 ms |
23596 KB |
Output is correct |
46 |
Correct |
408 ms |
23348 KB |
Output is correct |
47 |
Correct |
312 ms |
23872 KB |
Output is correct |
48 |
Correct |
229 ms |
15060 KB |
Output is correct |
49 |
Correct |
285 ms |
23676 KB |
Output is correct |
50 |
Correct |
392 ms |
22912 KB |
Output is correct |
51 |
Correct |
365 ms |
23488 KB |
Output is correct |