#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
using namespace std;
const long long N = 200100;
long long ans;
priority_queue<pair<long long,long long>> q1;
long long n,m,s,t,a,b;
vector<pair<long long,long long>> v1[N];
bool visited[N];
long long dp[N];
long long ds[N],dt[N],du[N],dv[N];
void dijkstra(long long *d,long long s){
for(long long i=1;i<=n;i++){
d[i] = 1e18;
}
d[s] = 0;
q1.push(make_pair(-d[s],s));
while(!q1.empty()){
auto hold = q1.top();
q1.pop();
for(auto e:v1[hold.second]){
if(d[e.first]>d[hold.second]+e.second){
d[e.first] = d[hold.second] + e.second;
q1.push(make_pair(-1*d[e.first],e.first));
}
}
}
}
long long dfs(long long s,long long check){
if(visited[s]){
return dp[s];
}
visited[s] = true;
dp[s] = du[s];
for(auto e:v1[s]){
if(check == 0){
if(ds[s]+e.second+dt[e.first] == ds[t]){
dp[s] = min(dp[s],dfs(e.first,check));
}
}else{
if(dt[s]+e.second+ds[e.first] == ds[t]){
dp[s] = min(dp[s],dfs(e.first,check));
}
}
}
ans = min(ans,dp[s]+dv[s]);
return dp[s];
}
int main() {
cin>>n>>m>>s>>t>>a>>b;
for(long long i=1;i<=m;i++){
long long x,y,z;
cin>>x>>y>>z;
v1[x].push_back(make_pair(y,z));
v1[y].push_back(make_pair(x,z));
}
dijkstra(du,a);
dijkstra(dv,b);
dijkstra(ds,s);
dijkstra(dt,t);
ans = du[b];
dfs(s,0);
for(long long i=1;i<=n;i++){
visited[i] = false;
}
dfs(t,1);
cout<<ans<<endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
482 ms |
23916 KB |
Output is correct |
2 |
Correct |
523 ms |
24176 KB |
Output is correct |
3 |
Correct |
598 ms |
27492 KB |
Output is correct |
4 |
Correct |
548 ms |
23892 KB |
Output is correct |
5 |
Correct |
586 ms |
23960 KB |
Output is correct |
6 |
Correct |
545 ms |
23916 KB |
Output is correct |
7 |
Correct |
630 ms |
24172 KB |
Output is correct |
8 |
Correct |
559 ms |
24092 KB |
Output is correct |
9 |
Correct |
489 ms |
24048 KB |
Output is correct |
10 |
Correct |
440 ms |
24040 KB |
Output is correct |
11 |
Correct |
191 ms |
18296 KB |
Output is correct |
12 |
Correct |
515 ms |
23880 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
519 ms |
25568 KB |
Output is correct |
2 |
Correct |
495 ms |
25448 KB |
Output is correct |
3 |
Correct |
526 ms |
25324 KB |
Output is correct |
4 |
Correct |
548 ms |
25576 KB |
Output is correct |
5 |
Correct |
693 ms |
25760 KB |
Output is correct |
6 |
Correct |
647 ms |
27084 KB |
Output is correct |
7 |
Correct |
702 ms |
27164 KB |
Output is correct |
8 |
Correct |
588 ms |
25580 KB |
Output is correct |
9 |
Correct |
603 ms |
25820 KB |
Output is correct |
10 |
Correct |
595 ms |
25332 KB |
Output is correct |
11 |
Correct |
255 ms |
19320 KB |
Output is correct |
12 |
Correct |
633 ms |
27368 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
6392 KB |
Output is correct |
2 |
Correct |
6 ms |
5112 KB |
Output is correct |
3 |
Correct |
6 ms |
5112 KB |
Output is correct |
4 |
Correct |
48 ms |
7724 KB |
Output is correct |
5 |
Correct |
28 ms |
6392 KB |
Output is correct |
6 |
Correct |
8 ms |
5116 KB |
Output is correct |
7 |
Correct |
8 ms |
5240 KB |
Output is correct |
8 |
Correct |
9 ms |
5240 KB |
Output is correct |
9 |
Correct |
6 ms |
5112 KB |
Output is correct |
10 |
Correct |
25 ms |
6392 KB |
Output is correct |
11 |
Correct |
5 ms |
5112 KB |
Output is correct |
12 |
Correct |
6 ms |
5112 KB |
Output is correct |
13 |
Correct |
6 ms |
5112 KB |
Output is correct |
14 |
Correct |
7 ms |
5112 KB |
Output is correct |
15 |
Correct |
7 ms |
5112 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
482 ms |
23916 KB |
Output is correct |
2 |
Correct |
523 ms |
24176 KB |
Output is correct |
3 |
Correct |
598 ms |
27492 KB |
Output is correct |
4 |
Correct |
548 ms |
23892 KB |
Output is correct |
5 |
Correct |
586 ms |
23960 KB |
Output is correct |
6 |
Correct |
545 ms |
23916 KB |
Output is correct |
7 |
Correct |
630 ms |
24172 KB |
Output is correct |
8 |
Correct |
559 ms |
24092 KB |
Output is correct |
9 |
Correct |
489 ms |
24048 KB |
Output is correct |
10 |
Correct |
440 ms |
24040 KB |
Output is correct |
11 |
Correct |
191 ms |
18296 KB |
Output is correct |
12 |
Correct |
515 ms |
23880 KB |
Output is correct |
13 |
Correct |
519 ms |
25568 KB |
Output is correct |
14 |
Correct |
495 ms |
25448 KB |
Output is correct |
15 |
Correct |
526 ms |
25324 KB |
Output is correct |
16 |
Correct |
548 ms |
25576 KB |
Output is correct |
17 |
Correct |
693 ms |
25760 KB |
Output is correct |
18 |
Correct |
647 ms |
27084 KB |
Output is correct |
19 |
Correct |
702 ms |
27164 KB |
Output is correct |
20 |
Correct |
588 ms |
25580 KB |
Output is correct |
21 |
Correct |
603 ms |
25820 KB |
Output is correct |
22 |
Correct |
595 ms |
25332 KB |
Output is correct |
23 |
Correct |
255 ms |
19320 KB |
Output is correct |
24 |
Correct |
633 ms |
27368 KB |
Output is correct |
25 |
Correct |
27 ms |
6392 KB |
Output is correct |
26 |
Correct |
6 ms |
5112 KB |
Output is correct |
27 |
Correct |
6 ms |
5112 KB |
Output is correct |
28 |
Correct |
48 ms |
7724 KB |
Output is correct |
29 |
Correct |
28 ms |
6392 KB |
Output is correct |
30 |
Correct |
8 ms |
5116 KB |
Output is correct |
31 |
Correct |
8 ms |
5240 KB |
Output is correct |
32 |
Correct |
9 ms |
5240 KB |
Output is correct |
33 |
Correct |
6 ms |
5112 KB |
Output is correct |
34 |
Correct |
25 ms |
6392 KB |
Output is correct |
35 |
Correct |
5 ms |
5112 KB |
Output is correct |
36 |
Correct |
6 ms |
5112 KB |
Output is correct |
37 |
Correct |
6 ms |
5112 KB |
Output is correct |
38 |
Correct |
7 ms |
5112 KB |
Output is correct |
39 |
Correct |
7 ms |
5112 KB |
Output is correct |
40 |
Correct |
532 ms |
23648 KB |
Output is correct |
41 |
Correct |
561 ms |
23968 KB |
Output is correct |
42 |
Correct |
559 ms |
23972 KB |
Output is correct |
43 |
Correct |
308 ms |
18676 KB |
Output is correct |
44 |
Correct |
212 ms |
18908 KB |
Output is correct |
45 |
Correct |
470 ms |
23532 KB |
Output is correct |
46 |
Correct |
492 ms |
23528 KB |
Output is correct |
47 |
Correct |
488 ms |
24164 KB |
Output is correct |
48 |
Correct |
284 ms |
16760 KB |
Output is correct |
49 |
Correct |
396 ms |
23268 KB |
Output is correct |
50 |
Correct |
538 ms |
23896 KB |
Output is correct |
51 |
Correct |
564 ms |
23660 KB |
Output is correct |