#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << " " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << " " << j << " " << #i << " " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<long long,int>pii;
typedef pair<int,pii>pi2;
vector<pii>adj[100005];
void solve(){
int n,m;
cin >> n >> m;
int a,b;
cin >> a >> b;
int s,t;
cin >> s >> t;
int temp,temp2,temp3;
for(int x=0;x<m;x++){
cin >> temp >> temp2 >> temp3;
adj[temp].push_back({temp2,temp3});
adj[temp2].push_back({temp,temp3});
}
int dist[n+5]; //a
int dist2[n+5]; //b
memset(dist,-1,sizeof(dist));
memset(dist2,-1,sizeof(dist2));
priority_queue<pii,vector<pii>,greater<pii>>pq;
dist[a]=0;
pq.push({0,a});
while(!pq.empty()){
pii cur=pq.top();
pq.pop();
int index=cur.second;
int d=cur.first;
if(dist[index]!=d) continue;
for(auto it:adj[index]){
int nx=it.first;
int nd=d+it.second;
if(dist[nx]!=-1&&dist[nx]<=nd) continue;
dist[nx]=nd;
pq.push({nd,nx});
}
}
dist2[b]=0;
pq.push({0,b});
while(!pq.empty()){
pii cur=pq.top();
pq.pop();
int index=cur.second;
int d=cur.first;
if(dist2[index]!=d) continue;
for(auto it:adj[index]){
int nx=it.first;
int nd=d+it.second;
if(dist2[nx]!=-1&&dist2[nx]<=nd) continue;
dist2[nx]=nd;
pq.push({nd,nx});
}
}
priority_queue<pi2,vector<pi2>,greater<pi2>>pq2;
int dist3[n+5][5];
memset(dist3,-1,sizeof(dist3));
dist3[s][0]=0;
pq2.push({0,{s,0}});
int target=dist[b];
while(!pq2.empty()){
pi2 cur=pq2.top();
pq2.pop();
int index=cur.second.first;
int k=cur.second.second;
int d=cur.first;
//show3(index,index,k,k,d,d);
for(auto it:adj[index]){
int nx=it.first;
int path=0;
if(dist[index]+it.second+dist2[nx]==target) path=1;
if(dist[nx]+it.second+dist2[index]==target) path=2;
if(k==0){
if( !(dist3[nx][k]!=-1&&dist3[nx][k]<=d+it.second) ){
dist3[nx][k]=d+it.second;
pq2.push({d+it.second,{nx,k}});
}
if( !(dist3[nx][path]!=-1&&dist3[nx][path]<=d) && (path!=0) ){
dist3[nx][path]=d;
pq2.push({d,{nx,path}});
}
}
else if(k==1||k==2){
if(path==k){
if( !(dist3[nx][path]!=-1&&dist3[nx][path]<=d) ){
dist3[nx][path]=d;
pq2.push({d,{nx,path}});
}
}
else{
if( !(dist3[nx][3]!=-1&&dist3[nx][3]<=d+it.second) ){
dist3[nx][3]=d+it.second;
pq2.push({d+it.second,{nx,3}});
}
}
}
else if(k==3){
if( !(dist3[nx][k]!=-1&&dist3[nx][k]<=d+it.second) ){
dist3[nx][k]=d+it.second;
pq2.push({d+it.second,{nx,k}});
}
}
}
}
int best=1e18;
for(int x=0;x<4;x++){
if(dist3[t][x]==-1) continue;
best=min(best,dist3[t][x]);
}
cout << best;
}
int32_t main(){
ios::sync_with_stdio(0);
cin.tie(0);
int t=1;
//cin >> t;
while(t--){
solve();
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
265 ms |
31660 KB |
Output is correct |
2 |
Correct |
252 ms |
26816 KB |
Output is correct |
3 |
Correct |
275 ms |
27976 KB |
Output is correct |
4 |
Correct |
190 ms |
28108 KB |
Output is correct |
5 |
Correct |
313 ms |
26560 KB |
Output is correct |
6 |
Correct |
245 ms |
32436 KB |
Output is correct |
7 |
Correct |
300 ms |
28112 KB |
Output is correct |
8 |
Correct |
299 ms |
26732 KB |
Output is correct |
9 |
Correct |
247 ms |
27588 KB |
Output is correct |
10 |
Correct |
231 ms |
28092 KB |
Output is correct |
11 |
Correct |
105 ms |
17544 KB |
Output is correct |
12 |
Correct |
278 ms |
27548 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
312 ms |
27068 KB |
Output is correct |
2 |
Correct |
308 ms |
26872 KB |
Output is correct |
3 |
Correct |
303 ms |
28160 KB |
Output is correct |
4 |
Correct |
295 ms |
26816 KB |
Output is correct |
5 |
Correct |
308 ms |
27516 KB |
Output is correct |
6 |
Correct |
318 ms |
27900 KB |
Output is correct |
7 |
Correct |
337 ms |
30900 KB |
Output is correct |
8 |
Correct |
325 ms |
27404 KB |
Output is correct |
9 |
Correct |
315 ms |
27652 KB |
Output is correct |
10 |
Correct |
329 ms |
26828 KB |
Output is correct |
11 |
Correct |
111 ms |
17212 KB |
Output is correct |
12 |
Correct |
307 ms |
28164 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
4188 KB |
Output is correct |
2 |
Correct |
1 ms |
2652 KB |
Output is correct |
3 |
Correct |
1 ms |
2652 KB |
Output is correct |
4 |
Correct |
14 ms |
5464 KB |
Output is correct |
5 |
Correct |
7 ms |
4188 KB |
Output is correct |
6 |
Correct |
2 ms |
2908 KB |
Output is correct |
7 |
Correct |
2 ms |
2908 KB |
Output is correct |
8 |
Correct |
2 ms |
2908 KB |
Output is correct |
9 |
Correct |
2 ms |
2908 KB |
Output is correct |
10 |
Correct |
7 ms |
4184 KB |
Output is correct |
11 |
Correct |
1 ms |
2648 KB |
Output is correct |
12 |
Correct |
1 ms |
2648 KB |
Output is correct |
13 |
Correct |
1 ms |
2652 KB |
Output is correct |
14 |
Correct |
2 ms |
2908 KB |
Output is correct |
15 |
Correct |
1 ms |
2908 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
265 ms |
31660 KB |
Output is correct |
2 |
Correct |
252 ms |
26816 KB |
Output is correct |
3 |
Correct |
275 ms |
27976 KB |
Output is correct |
4 |
Correct |
190 ms |
28108 KB |
Output is correct |
5 |
Correct |
313 ms |
26560 KB |
Output is correct |
6 |
Correct |
245 ms |
32436 KB |
Output is correct |
7 |
Correct |
300 ms |
28112 KB |
Output is correct |
8 |
Correct |
299 ms |
26732 KB |
Output is correct |
9 |
Correct |
247 ms |
27588 KB |
Output is correct |
10 |
Correct |
231 ms |
28092 KB |
Output is correct |
11 |
Correct |
105 ms |
17544 KB |
Output is correct |
12 |
Correct |
278 ms |
27548 KB |
Output is correct |
13 |
Correct |
312 ms |
27068 KB |
Output is correct |
14 |
Correct |
308 ms |
26872 KB |
Output is correct |
15 |
Correct |
303 ms |
28160 KB |
Output is correct |
16 |
Correct |
295 ms |
26816 KB |
Output is correct |
17 |
Correct |
308 ms |
27516 KB |
Output is correct |
18 |
Correct |
318 ms |
27900 KB |
Output is correct |
19 |
Correct |
337 ms |
30900 KB |
Output is correct |
20 |
Correct |
325 ms |
27404 KB |
Output is correct |
21 |
Correct |
315 ms |
27652 KB |
Output is correct |
22 |
Correct |
329 ms |
26828 KB |
Output is correct |
23 |
Correct |
111 ms |
17212 KB |
Output is correct |
24 |
Correct |
307 ms |
28164 KB |
Output is correct |
25 |
Correct |
8 ms |
4188 KB |
Output is correct |
26 |
Correct |
1 ms |
2652 KB |
Output is correct |
27 |
Correct |
1 ms |
2652 KB |
Output is correct |
28 |
Correct |
14 ms |
5464 KB |
Output is correct |
29 |
Correct |
7 ms |
4188 KB |
Output is correct |
30 |
Correct |
2 ms |
2908 KB |
Output is correct |
31 |
Correct |
2 ms |
2908 KB |
Output is correct |
32 |
Correct |
2 ms |
2908 KB |
Output is correct |
33 |
Correct |
2 ms |
2908 KB |
Output is correct |
34 |
Correct |
7 ms |
4184 KB |
Output is correct |
35 |
Correct |
1 ms |
2648 KB |
Output is correct |
36 |
Correct |
1 ms |
2648 KB |
Output is correct |
37 |
Correct |
1 ms |
2652 KB |
Output is correct |
38 |
Correct |
2 ms |
2908 KB |
Output is correct |
39 |
Correct |
1 ms |
2908 KB |
Output is correct |
40 |
Correct |
251 ms |
31772 KB |
Output is correct |
41 |
Correct |
238 ms |
25836 KB |
Output is correct |
42 |
Correct |
248 ms |
26164 KB |
Output is correct |
43 |
Correct |
158 ms |
17100 KB |
Output is correct |
44 |
Correct |
145 ms |
17104 KB |
Output is correct |
45 |
Correct |
326 ms |
26320 KB |
Output is correct |
46 |
Correct |
302 ms |
27592 KB |
Output is correct |
47 |
Correct |
294 ms |
28136 KB |
Output is correct |
48 |
Correct |
127 ms |
16644 KB |
Output is correct |
49 |
Correct |
196 ms |
31896 KB |
Output is correct |
50 |
Correct |
367 ms |
30376 KB |
Output is correct |
51 |
Correct |
366 ms |
29568 KB |
Output is correct |