#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> pii;
const LL MAXN=100005,INF=1e18;
vector<pii> adj[MAXN];
LL city[4];
LL s,t,u,v,dp[MAXN][2],dist[4][MAXN];
LL DP(LL now,LL stat){
LL &ret=dp[now][stat];
if(ret!=-1)return ret;
ret=dist[3][now];
for(auto nxt : adj[now]){
if(stat==0){
if(dist[0][now]+nxt.second+dist[1][nxt.first]==dist[0][t])ret=min(ret,DP(nxt.first,stat));
}
else{
if(dist[1][now]+nxt.second+dist[0][nxt.first]==dist[1][s])ret=min(ret,DP(nxt.first,stat));
}
}
return ret;
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
LL n,m,U,V,w;
cin >> n >> m >> s >> t >> u >> v;
for(LL i=1;i<=m;i++){
cin >> U >> V >> w;
adj[U].push_back({V,w});
adj[V].push_back({U,w});
}
city[0]=s;city[1]=t;city[2]=u;city[3]=v;
for(LL i=0;i<4;i++){
for(LL j=1;j<=n;j++)dist[i][j]=INF;
dist[i][city[i]]=0;
priority_queue<pii,vector<pii>,greater<pii> > PQ;
PQ.push({0,city[i]});
while(!PQ.empty()){
pii now=PQ.top();
PQ.pop();
if(dist[i][now.second]<now.first)continue;
for(auto nxt : adj[now.second]){
if(dist[i][now.second]+nxt.second<dist[i][nxt.first]){
dist[i][nxt.first]=dist[i][now.second]+nxt.second;
PQ.push({dist[i][nxt.first],nxt.first});
}
}
}
}
memset(dp,-1,sizeof(dp));
LL ans=dist[2][v];
for(LL i=1;i<=n;i++){
if(dist[0][i]+dist[1][i]==dist[0][t])ans=min(ans,dist[2][i]+min(DP(i,0),DP(i,1)));
}
cout << ans << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
347 ms |
19528 KB |
Output is correct |
2 |
Correct |
370 ms |
18328 KB |
Output is correct |
3 |
Correct |
386 ms |
22428 KB |
Output is correct |
4 |
Correct |
343 ms |
23032 KB |
Output is correct |
5 |
Correct |
371 ms |
21600 KB |
Output is correct |
6 |
Correct |
367 ms |
23208 KB |
Output is correct |
7 |
Correct |
379 ms |
21536 KB |
Output is correct |
8 |
Correct |
380 ms |
21528 KB |
Output is correct |
9 |
Correct |
356 ms |
22676 KB |
Output is correct |
10 |
Correct |
307 ms |
22348 KB |
Output is correct |
11 |
Correct |
160 ms |
17528 KB |
Output is correct |
12 |
Correct |
363 ms |
22276 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
392 ms |
20088 KB |
Output is correct |
2 |
Correct |
383 ms |
23280 KB |
Output is correct |
3 |
Correct |
394 ms |
23420 KB |
Output is correct |
4 |
Correct |
401 ms |
23856 KB |
Output is correct |
5 |
Correct |
400 ms |
23292 KB |
Output is correct |
6 |
Correct |
406 ms |
25436 KB |
Output is correct |
7 |
Correct |
455 ms |
25284 KB |
Output is correct |
8 |
Correct |
383 ms |
22804 KB |
Output is correct |
9 |
Correct |
422 ms |
23432 KB |
Output is correct |
10 |
Correct |
390 ms |
23408 KB |
Output is correct |
11 |
Correct |
188 ms |
19064 KB |
Output is correct |
12 |
Correct |
392 ms |
25068 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
5632 KB |
Output is correct |
2 |
Correct |
3 ms |
4352 KB |
Output is correct |
3 |
Correct |
3 ms |
4352 KB |
Output is correct |
4 |
Correct |
19 ms |
7040 KB |
Output is correct |
5 |
Correct |
11 ms |
5632 KB |
Output is correct |
6 |
Correct |
4 ms |
4352 KB |
Output is correct |
7 |
Correct |
4 ms |
4352 KB |
Output is correct |
8 |
Correct |
5 ms |
4480 KB |
Output is correct |
9 |
Correct |
4 ms |
4352 KB |
Output is correct |
10 |
Correct |
12 ms |
5632 KB |
Output is correct |
11 |
Correct |
3 ms |
4352 KB |
Output is correct |
12 |
Correct |
3 ms |
4352 KB |
Output is correct |
13 |
Correct |
3 ms |
4352 KB |
Output is correct |
14 |
Correct |
5 ms |
4384 KB |
Output is correct |
15 |
Correct |
4 ms |
4352 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
347 ms |
19528 KB |
Output is correct |
2 |
Correct |
370 ms |
18328 KB |
Output is correct |
3 |
Correct |
386 ms |
22428 KB |
Output is correct |
4 |
Correct |
343 ms |
23032 KB |
Output is correct |
5 |
Correct |
371 ms |
21600 KB |
Output is correct |
6 |
Correct |
367 ms |
23208 KB |
Output is correct |
7 |
Correct |
379 ms |
21536 KB |
Output is correct |
8 |
Correct |
380 ms |
21528 KB |
Output is correct |
9 |
Correct |
356 ms |
22676 KB |
Output is correct |
10 |
Correct |
307 ms |
22348 KB |
Output is correct |
11 |
Correct |
160 ms |
17528 KB |
Output is correct |
12 |
Correct |
363 ms |
22276 KB |
Output is correct |
13 |
Correct |
392 ms |
20088 KB |
Output is correct |
14 |
Correct |
383 ms |
23280 KB |
Output is correct |
15 |
Correct |
394 ms |
23420 KB |
Output is correct |
16 |
Correct |
401 ms |
23856 KB |
Output is correct |
17 |
Correct |
400 ms |
23292 KB |
Output is correct |
18 |
Correct |
406 ms |
25436 KB |
Output is correct |
19 |
Correct |
455 ms |
25284 KB |
Output is correct |
20 |
Correct |
383 ms |
22804 KB |
Output is correct |
21 |
Correct |
422 ms |
23432 KB |
Output is correct |
22 |
Correct |
390 ms |
23408 KB |
Output is correct |
23 |
Correct |
188 ms |
19064 KB |
Output is correct |
24 |
Correct |
392 ms |
25068 KB |
Output is correct |
25 |
Correct |
11 ms |
5632 KB |
Output is correct |
26 |
Correct |
3 ms |
4352 KB |
Output is correct |
27 |
Correct |
3 ms |
4352 KB |
Output is correct |
28 |
Correct |
19 ms |
7040 KB |
Output is correct |
29 |
Correct |
11 ms |
5632 KB |
Output is correct |
30 |
Correct |
4 ms |
4352 KB |
Output is correct |
31 |
Correct |
4 ms |
4352 KB |
Output is correct |
32 |
Correct |
5 ms |
4480 KB |
Output is correct |
33 |
Correct |
4 ms |
4352 KB |
Output is correct |
34 |
Correct |
12 ms |
5632 KB |
Output is correct |
35 |
Correct |
3 ms |
4352 KB |
Output is correct |
36 |
Correct |
3 ms |
4352 KB |
Output is correct |
37 |
Correct |
3 ms |
4352 KB |
Output is correct |
38 |
Correct |
5 ms |
4384 KB |
Output is correct |
39 |
Correct |
4 ms |
4352 KB |
Output is correct |
40 |
Correct |
336 ms |
23160 KB |
Output is correct |
41 |
Correct |
358 ms |
22288 KB |
Output is correct |
42 |
Correct |
361 ms |
22548 KB |
Output is correct |
43 |
Correct |
206 ms |
18168 KB |
Output is correct |
44 |
Correct |
212 ms |
18552 KB |
Output is correct |
45 |
Correct |
392 ms |
22344 KB |
Output is correct |
46 |
Correct |
403 ms |
21240 KB |
Output is correct |
47 |
Correct |
356 ms |
23300 KB |
Output is correct |
48 |
Correct |
211 ms |
15736 KB |
Output is correct |
49 |
Correct |
305 ms |
23028 KB |
Output is correct |
50 |
Correct |
384 ms |
21492 KB |
Output is correct |
51 |
Correct |
404 ms |
21416 KB |
Output is correct |