#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define PB push_back
#define EB emplace_back
#define bit(n,i) ((n>>i)&1)
#define all(x) x.begin(),x.end()
#define ll long long
#define sz(x) (int)x.size()
#define TASK "cf"
using namespace std;
const int maxn=1e5+5;
vector<pair<int,int>> adj[maxn];
vector<int>to[maxn],adj2[maxn],radj[maxn];
int n,m;
int s,t,ss,tt;
bool check[maxn],check2[4][maxn];
ll d[maxn],d2[4][maxn];
void dijkstra(){
memset(check,0,sizeof(check));
memset(d,60,sizeof(d));
priority_queue<pair<ll,int>> pq;
pq.push(mp(0,s));
d[s]=0;
while(!pq.empty()){
int u=pq.top().se,w=pq.top().fi;
pq.pop();
if (check[u]) continue;
check[u]=1;
for (auto v:adj[u]) {
if (d[v.fi]>d[u]+v.se) {
to[v.fi].clear();
to[v.fi].PB(u);
d[v.fi]=d[u]+v.se;
pq.push(mp(-d[v.fi],v.fi));
}
else if (d[v.fi]==d[u]+v.se) to[v.fi].PB(u);
}
}
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>m>>s>>t>>ss>>tt;
for (int i=1;i<=m;i++) {
int x,y,z; cin>>x>>y>>z;
adj[x].PB(mp(y,z));
adj[y].PB(mp(x,z));
}
dijkstra();
memset(check,0,sizeof(check));
queue<int> q;
q.push(t);
check[t]=1;
while(!q.empty()){
int u=q.front();q.pop();
for(auto v:to[u]) {
adj2[u].PB(v);
radj[v].PB(u);
if (!check[v]) {
check[v]=1;q.push(v);
}
}
}
priority_queue<pair<ll,pair<int,int>>>pq;
memset(d2,60,sizeof(d2));
d2[0][ss]=0;
pq.push(mp(0,mp(0,ss)));
while(!pq.empty()){
int u=pq.top().se.se,rev=pq.top().se.fi;
ll w=pq.top().fi;pq.pop();
if (u==tt) {cout<<d2[rev][u]<<"\n"; return 0;}
if (check2[rev][u]) continue;
check2[rev][u]=1;
for (auto v:adj[u]) {
int ne;
if(rev==0) ne=0; else ne=3;
if (d2[ne][v.fi]>d2[rev][u]+v.se) {
d2[ne][v.fi]=d2[rev][u]+v.se;
pq.push(mp(-d2[ne][v.fi],mp(ne,v.fi)));
}
}
if (rev==0||rev==1) {
for (auto v:adj2[u]) {
if (d2[1][v]>d2[rev][u]) {
d2[1][v]=d2[rev][u];
pq.push(mp(-d2[1][v],mp(1,v)));
}
}
}
if (rev==0 || rev==2) {
for (auto v:radj[u]){
if (d2[2][v]>d2[rev][u]) {
d2[2][v]=d2[rev][u];
pq.push(mp(-d2[2][v],mp(2,v)));
}
}
}
}
return 0;
}
Compilation message
commuter_pass.cpp: In function 'void dijkstra()':
commuter_pass.cpp:31:27: warning: unused variable 'w' [-Wunused-variable]
31 | int u=pq.top().se,w=pq.top().fi;
| ^
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:82:12: warning: unused variable 'w' [-Wunused-variable]
82 | ll w=pq.top().fi;pq.pop();
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
154 ms |
33940 KB |
Output is correct |
2 |
Correct |
159 ms |
31000 KB |
Output is correct |
3 |
Correct |
208 ms |
35280 KB |
Output is correct |
4 |
Correct |
156 ms |
29208 KB |
Output is correct |
5 |
Correct |
200 ms |
35040 KB |
Output is correct |
6 |
Correct |
169 ms |
34368 KB |
Output is correct |
7 |
Correct |
127 ms |
31616 KB |
Output is correct |
8 |
Correct |
130 ms |
31480 KB |
Output is correct |
9 |
Correct |
149 ms |
30284 KB |
Output is correct |
10 |
Correct |
123 ms |
30612 KB |
Output is correct |
11 |
Correct |
144 ms |
26064 KB |
Output is correct |
12 |
Correct |
112 ms |
27560 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
141 ms |
28824 KB |
Output is correct |
2 |
Correct |
262 ms |
31080 KB |
Output is correct |
3 |
Correct |
136 ms |
29400 KB |
Output is correct |
4 |
Correct |
143 ms |
31328 KB |
Output is correct |
5 |
Correct |
194 ms |
31608 KB |
Output is correct |
6 |
Correct |
220 ms |
34260 KB |
Output is correct |
7 |
Correct |
174 ms |
33364 KB |
Output is correct |
8 |
Correct |
188 ms |
31088 KB |
Output is correct |
9 |
Correct |
138 ms |
31584 KB |
Output is correct |
10 |
Correct |
119 ms |
28024 KB |
Output is correct |
11 |
Correct |
106 ms |
28536 KB |
Output is correct |
12 |
Correct |
248 ms |
35452 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
15452 KB |
Output is correct |
2 |
Correct |
4 ms |
14172 KB |
Output is correct |
3 |
Correct |
4 ms |
14172 KB |
Output is correct |
4 |
Correct |
13 ms |
16220 KB |
Output is correct |
5 |
Correct |
8 ms |
15200 KB |
Output is correct |
6 |
Correct |
4 ms |
14172 KB |
Output is correct |
7 |
Correct |
4 ms |
14172 KB |
Output is correct |
8 |
Correct |
4 ms |
14428 KB |
Output is correct |
9 |
Correct |
4 ms |
14172 KB |
Output is correct |
10 |
Correct |
8 ms |
15196 KB |
Output is correct |
11 |
Correct |
3 ms |
14172 KB |
Output is correct |
12 |
Correct |
3 ms |
14076 KB |
Output is correct |
13 |
Correct |
4 ms |
14168 KB |
Output is correct |
14 |
Correct |
3 ms |
14172 KB |
Output is correct |
15 |
Correct |
4 ms |
14172 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
154 ms |
33940 KB |
Output is correct |
2 |
Correct |
159 ms |
31000 KB |
Output is correct |
3 |
Correct |
208 ms |
35280 KB |
Output is correct |
4 |
Correct |
156 ms |
29208 KB |
Output is correct |
5 |
Correct |
200 ms |
35040 KB |
Output is correct |
6 |
Correct |
169 ms |
34368 KB |
Output is correct |
7 |
Correct |
127 ms |
31616 KB |
Output is correct |
8 |
Correct |
130 ms |
31480 KB |
Output is correct |
9 |
Correct |
149 ms |
30284 KB |
Output is correct |
10 |
Correct |
123 ms |
30612 KB |
Output is correct |
11 |
Correct |
144 ms |
26064 KB |
Output is correct |
12 |
Correct |
112 ms |
27560 KB |
Output is correct |
13 |
Correct |
141 ms |
28824 KB |
Output is correct |
14 |
Correct |
262 ms |
31080 KB |
Output is correct |
15 |
Correct |
136 ms |
29400 KB |
Output is correct |
16 |
Correct |
143 ms |
31328 KB |
Output is correct |
17 |
Correct |
194 ms |
31608 KB |
Output is correct |
18 |
Correct |
220 ms |
34260 KB |
Output is correct |
19 |
Correct |
174 ms |
33364 KB |
Output is correct |
20 |
Correct |
188 ms |
31088 KB |
Output is correct |
21 |
Correct |
138 ms |
31584 KB |
Output is correct |
22 |
Correct |
119 ms |
28024 KB |
Output is correct |
23 |
Correct |
106 ms |
28536 KB |
Output is correct |
24 |
Correct |
248 ms |
35452 KB |
Output is correct |
25 |
Correct |
9 ms |
15452 KB |
Output is correct |
26 |
Correct |
4 ms |
14172 KB |
Output is correct |
27 |
Correct |
4 ms |
14172 KB |
Output is correct |
28 |
Correct |
13 ms |
16220 KB |
Output is correct |
29 |
Correct |
8 ms |
15200 KB |
Output is correct |
30 |
Correct |
4 ms |
14172 KB |
Output is correct |
31 |
Correct |
4 ms |
14172 KB |
Output is correct |
32 |
Correct |
4 ms |
14428 KB |
Output is correct |
33 |
Correct |
4 ms |
14172 KB |
Output is correct |
34 |
Correct |
8 ms |
15196 KB |
Output is correct |
35 |
Correct |
3 ms |
14172 KB |
Output is correct |
36 |
Correct |
3 ms |
14076 KB |
Output is correct |
37 |
Correct |
4 ms |
14168 KB |
Output is correct |
38 |
Correct |
3 ms |
14172 KB |
Output is correct |
39 |
Correct |
4 ms |
14172 KB |
Output is correct |
40 |
Correct |
166 ms |
33448 KB |
Output is correct |
41 |
Correct |
141 ms |
28696 KB |
Output is correct |
42 |
Correct |
134 ms |
29040 KB |
Output is correct |
43 |
Correct |
98 ms |
30920 KB |
Output is correct |
44 |
Correct |
100 ms |
30916 KB |
Output is correct |
45 |
Correct |
203 ms |
35864 KB |
Output is correct |
46 |
Correct |
200 ms |
38452 KB |
Output is correct |
47 |
Correct |
170 ms |
29920 KB |
Output is correct |
48 |
Correct |
111 ms |
30300 KB |
Output is correct |
49 |
Correct |
136 ms |
34304 KB |
Output is correct |
50 |
Correct |
208 ms |
36244 KB |
Output is correct |
51 |
Correct |
153 ms |
33408 KB |
Output is correct |