#include<bits/stdc++.h>
#define st first
#define nd second
using namespace std;
using ll=long long;
const int N=1e5+5;
const ll INF=1e18;
vector<pair<int, int> > E[N];
int n;
vector<ll> dij(int s){
vector<ll> dist(n+1, INF);
vector<bool> vis(n+1);
dist[s]=0;
priority_queue<pair<ll, int> > Q;
for(int i=1; i<=n; i++){
Q.push({-dist[i], i});
}
while(Q.size()){
//cout<<"a";
int v=Q.top().nd;
Q.pop();
if(vis[v])continue;
vis[v]=1;
for(auto u:E[v]){
if(dist[v]+u.nd<dist[u.st]){
dist[u.st]=dist[v]+u.nd;
Q.push({-dist[u.st], u.st});
}
}
}
return dist;
}
vector<ll> ds,dt,du,dv;
ll opt[N];
int main(){
int m;
cin>>n>>m;
int s, t;
int U, V;
cin>>s>>t>>U>>V;
for(int i=0; i<m; i++){
int u, v, w;
cin>>u>>v>>w;
E[u].push_back({v, w});
E[v].push_back({u, w});
}
ds=dij(s), dt=dij(t), du=dij(U), dv=dij(V);
//for(auto i:ds)cout<<i<<" ";
ll ans=du[V];
vector<int> kol(n);
for(int i=0; i<n; i++)kol[i]=i+1;
sort(kol.begin(), kol.end(), [](int a, int b){return ds[a]<ds[b];});
for(int i=1; i<=n; i++)opt[i]=du[i];
for(int v:kol){
for(auto u:E[v]){
if(dt[v]+ds[u.st]+u.nd==ds[t]){
opt[v]=min(opt[v], opt[u.st]);
}
}
if(dt[v]+ds[v]==ds[t])ans=min(ans, opt[v]+dv[v]);
}
//reverse(kol.begin(), kol.end());
for(int i=1; i<=n; i++)opt[i]=dv[i];
for(int v:kol){
for(auto u:E[v]){
if(dt[v]+ds[u.st]+u.nd==ds[t]){
opt[v]=min(opt[v], opt[u.st]);
}
}
//cout<<v<<" "<<opt[v]<<"\n";
if(dt[v]+ds[v]==ds[t])ans=min(ans, opt[v]+du[v]);
}
cout<<ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
533 ms |
22856 KB |
Output is correct |
2 |
Correct |
506 ms |
22084 KB |
Output is correct |
3 |
Correct |
514 ms |
22084 KB |
Output is correct |
4 |
Correct |
546 ms |
22576 KB |
Output is correct |
5 |
Correct |
490 ms |
22072 KB |
Output is correct |
6 |
Correct |
612 ms |
22668 KB |
Output is correct |
7 |
Correct |
576 ms |
21832 KB |
Output is correct |
8 |
Correct |
508 ms |
21984 KB |
Output is correct |
9 |
Correct |
525 ms |
22888 KB |
Output is correct |
10 |
Correct |
497 ms |
22944 KB |
Output is correct |
11 |
Correct |
289 ms |
14596 KB |
Output is correct |
12 |
Correct |
521 ms |
22696 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
537 ms |
22340 KB |
Output is correct |
2 |
Correct |
548 ms |
22244 KB |
Output is correct |
3 |
Correct |
541 ms |
22040 KB |
Output is correct |
4 |
Correct |
569 ms |
21936 KB |
Output is correct |
5 |
Correct |
584 ms |
22084 KB |
Output is correct |
6 |
Correct |
527 ms |
22204 KB |
Output is correct |
7 |
Correct |
525 ms |
22232 KB |
Output is correct |
8 |
Correct |
527 ms |
22052 KB |
Output is correct |
9 |
Correct |
585 ms |
22024 KB |
Output is correct |
10 |
Correct |
534 ms |
22052 KB |
Output is correct |
11 |
Correct |
290 ms |
14544 KB |
Output is correct |
12 |
Correct |
514 ms |
22512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
3736 KB |
Output is correct |
2 |
Correct |
2 ms |
2672 KB |
Output is correct |
3 |
Correct |
3 ms |
2644 KB |
Output is correct |
4 |
Correct |
40 ms |
4812 KB |
Output is correct |
5 |
Correct |
23 ms |
3644 KB |
Output is correct |
6 |
Correct |
3 ms |
2772 KB |
Output is correct |
7 |
Correct |
6 ms |
2772 KB |
Output is correct |
8 |
Correct |
5 ms |
2800 KB |
Output is correct |
9 |
Correct |
3 ms |
2772 KB |
Output is correct |
10 |
Correct |
21 ms |
3668 KB |
Output is correct |
11 |
Correct |
3 ms |
2644 KB |
Output is correct |
12 |
Correct |
2 ms |
2664 KB |
Output is correct |
13 |
Correct |
2 ms |
2644 KB |
Output is correct |
14 |
Correct |
3 ms |
2676 KB |
Output is correct |
15 |
Correct |
3 ms |
2644 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
533 ms |
22856 KB |
Output is correct |
2 |
Correct |
506 ms |
22084 KB |
Output is correct |
3 |
Correct |
514 ms |
22084 KB |
Output is correct |
4 |
Correct |
546 ms |
22576 KB |
Output is correct |
5 |
Correct |
490 ms |
22072 KB |
Output is correct |
6 |
Correct |
612 ms |
22668 KB |
Output is correct |
7 |
Correct |
576 ms |
21832 KB |
Output is correct |
8 |
Correct |
508 ms |
21984 KB |
Output is correct |
9 |
Correct |
525 ms |
22888 KB |
Output is correct |
10 |
Correct |
497 ms |
22944 KB |
Output is correct |
11 |
Correct |
289 ms |
14596 KB |
Output is correct |
12 |
Correct |
521 ms |
22696 KB |
Output is correct |
13 |
Correct |
537 ms |
22340 KB |
Output is correct |
14 |
Correct |
548 ms |
22244 KB |
Output is correct |
15 |
Correct |
541 ms |
22040 KB |
Output is correct |
16 |
Correct |
569 ms |
21936 KB |
Output is correct |
17 |
Correct |
584 ms |
22084 KB |
Output is correct |
18 |
Correct |
527 ms |
22204 KB |
Output is correct |
19 |
Correct |
525 ms |
22232 KB |
Output is correct |
20 |
Correct |
527 ms |
22052 KB |
Output is correct |
21 |
Correct |
585 ms |
22024 KB |
Output is correct |
22 |
Correct |
534 ms |
22052 KB |
Output is correct |
23 |
Correct |
290 ms |
14544 KB |
Output is correct |
24 |
Correct |
514 ms |
22512 KB |
Output is correct |
25 |
Correct |
21 ms |
3736 KB |
Output is correct |
26 |
Correct |
2 ms |
2672 KB |
Output is correct |
27 |
Correct |
3 ms |
2644 KB |
Output is correct |
28 |
Correct |
40 ms |
4812 KB |
Output is correct |
29 |
Correct |
23 ms |
3644 KB |
Output is correct |
30 |
Correct |
3 ms |
2772 KB |
Output is correct |
31 |
Correct |
6 ms |
2772 KB |
Output is correct |
32 |
Correct |
5 ms |
2800 KB |
Output is correct |
33 |
Correct |
3 ms |
2772 KB |
Output is correct |
34 |
Correct |
21 ms |
3668 KB |
Output is correct |
35 |
Correct |
3 ms |
2644 KB |
Output is correct |
36 |
Correct |
2 ms |
2664 KB |
Output is correct |
37 |
Correct |
2 ms |
2644 KB |
Output is correct |
38 |
Correct |
3 ms |
2676 KB |
Output is correct |
39 |
Correct |
3 ms |
2644 KB |
Output is correct |
40 |
Correct |
579 ms |
23132 KB |
Output is correct |
41 |
Correct |
524 ms |
22776 KB |
Output is correct |
42 |
Correct |
573 ms |
22836 KB |
Output is correct |
43 |
Correct |
319 ms |
14556 KB |
Output is correct |
44 |
Correct |
300 ms |
14548 KB |
Output is correct |
45 |
Correct |
479 ms |
20944 KB |
Output is correct |
46 |
Correct |
462 ms |
21400 KB |
Output is correct |
47 |
Correct |
521 ms |
22524 KB |
Output is correct |
48 |
Correct |
275 ms |
14084 KB |
Output is correct |
49 |
Correct |
454 ms |
22684 KB |
Output is correct |
50 |
Correct |
486 ms |
21836 KB |
Output is correct |
51 |
Correct |
515 ms |
21588 KB |
Output is correct |