#include<bits/stdc++.h>
using namespace std;
using lol=long long int;
#define endl "\n"
const lol mod1=1e9+7,mod2=998244353,mod3=100000000000000003,hashpr=31;
const lol inf=9e18+8;
const double eps=1e-12;
const double PI=acos(-1.0);
const int N=1e5+5;
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace __gnu_pbds;
using ordered_set_type=lol;
typedef tree<ordered_set_type,null_type,less<ordered_set_type>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<pair<int,lol>> g[N];
vector<lol> d_s(N,inf),d_t(N,inf),d_u(N,inf),d_v(N,inf),m_s(N,inf),m_t(N,inf);
int n,m,s,t,u,v;
void shortest_path(int src,vector<lol>& d,vector<lol>& m,bool calc_m=false){
//insert {-dist,v}
priority_queue<pair<lol,int>> pq;
pq.push({0,src});
d[src]=0;
if(calc_m) m[src]=d_v[src];
while(!pq.empty()){
auto [ndist,u] = pq.top();
pq.pop();
if(-ndist>d[u]) continue;
for(auto [v,w]:g[u]){
if(d[u]+w<d[v]){
d[v]=d[u]+w;
pq.push({-d[v],v});
if(calc_m){
m[v]=min({m[u],d_v[v]});
}
}else if(d[u]+w==d[v]){
lol old=m[v];
if(calc_m){
m[v]=min({m[v],m[u],d_v[v]});
}
if(old!=m[v]){
pq.push({-d[v],v});
}
}
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int _=1;
//cin>>_;
while(_--)
{
cin>>n>>m>>s>>t>>u>>v;
for(int i=0;i<m;i++){
lol a,b,c;
cin>>a>>b>>c;
g[a].push_back({b,c});
g[b].push_back({a,c});
}
shortest_path(u,d_u,m_s);
shortest_path(v,d_v,m_s);
shortest_path(s,d_s,m_s,true);
shortest_path(t,d_t,m_t,true);
lol ans=inf;
for(int i=1;i<=n;i++){
if(d_s[i]+d_t[i]==d_s[t]){
lol du=d_u[i];
lol dv=min(m_s[i],m_t[i]);
ans=min(ans,du+dv);
}
}
cout<<min(d_u[v],ans);
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
219 ms |
21108 KB |
Output is correct |
2 |
Correct |
221 ms |
19736 KB |
Output is correct |
3 |
Correct |
212 ms |
24560 KB |
Output is correct |
4 |
Correct |
231 ms |
24816 KB |
Output is correct |
5 |
Correct |
245 ms |
22996 KB |
Output is correct |
6 |
Correct |
213 ms |
24852 KB |
Output is correct |
7 |
Correct |
207 ms |
23160 KB |
Output is correct |
8 |
Correct |
205 ms |
23272 KB |
Output is correct |
9 |
Correct |
213 ms |
24044 KB |
Output is correct |
10 |
Correct |
166 ms |
24244 KB |
Output is correct |
11 |
Correct |
75 ms |
14768 KB |
Output is correct |
12 |
Correct |
214 ms |
23976 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
273 ms |
20168 KB |
Output is correct |
2 |
Correct |
248 ms |
19816 KB |
Output is correct |
3 |
Correct |
251 ms |
23136 KB |
Output is correct |
4 |
Correct |
226 ms |
23228 KB |
Output is correct |
5 |
Correct |
230 ms |
23204 KB |
Output is correct |
6 |
Correct |
231 ms |
23728 KB |
Output is correct |
7 |
Correct |
224 ms |
23320 KB |
Output is correct |
8 |
Correct |
278 ms |
23308 KB |
Output is correct |
9 |
Correct |
217 ms |
23448 KB |
Output is correct |
10 |
Correct |
213 ms |
23220 KB |
Output is correct |
11 |
Correct |
84 ms |
14752 KB |
Output is correct |
12 |
Correct |
222 ms |
23640 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
8792 KB |
Output is correct |
2 |
Correct |
3 ms |
7516 KB |
Output is correct |
3 |
Correct |
3 ms |
7516 KB |
Output is correct |
4 |
Correct |
13 ms |
10200 KB |
Output is correct |
5 |
Correct |
9 ms |
8796 KB |
Output is correct |
6 |
Correct |
3 ms |
7516 KB |
Output is correct |
7 |
Correct |
4 ms |
7516 KB |
Output is correct |
8 |
Correct |
4 ms |
7516 KB |
Output is correct |
9 |
Correct |
3 ms |
7768 KB |
Output is correct |
10 |
Correct |
7 ms |
8796 KB |
Output is correct |
11 |
Correct |
3 ms |
7516 KB |
Output is correct |
12 |
Correct |
3 ms |
7516 KB |
Output is correct |
13 |
Correct |
3 ms |
7516 KB |
Output is correct |
14 |
Correct |
3 ms |
7516 KB |
Output is correct |
15 |
Correct |
3 ms |
7516 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
219 ms |
21108 KB |
Output is correct |
2 |
Correct |
221 ms |
19736 KB |
Output is correct |
3 |
Correct |
212 ms |
24560 KB |
Output is correct |
4 |
Correct |
231 ms |
24816 KB |
Output is correct |
5 |
Correct |
245 ms |
22996 KB |
Output is correct |
6 |
Correct |
213 ms |
24852 KB |
Output is correct |
7 |
Correct |
207 ms |
23160 KB |
Output is correct |
8 |
Correct |
205 ms |
23272 KB |
Output is correct |
9 |
Correct |
213 ms |
24044 KB |
Output is correct |
10 |
Correct |
166 ms |
24244 KB |
Output is correct |
11 |
Correct |
75 ms |
14768 KB |
Output is correct |
12 |
Correct |
214 ms |
23976 KB |
Output is correct |
13 |
Correct |
273 ms |
20168 KB |
Output is correct |
14 |
Correct |
248 ms |
19816 KB |
Output is correct |
15 |
Correct |
251 ms |
23136 KB |
Output is correct |
16 |
Correct |
226 ms |
23228 KB |
Output is correct |
17 |
Correct |
230 ms |
23204 KB |
Output is correct |
18 |
Correct |
231 ms |
23728 KB |
Output is correct |
19 |
Correct |
224 ms |
23320 KB |
Output is correct |
20 |
Correct |
278 ms |
23308 KB |
Output is correct |
21 |
Correct |
217 ms |
23448 KB |
Output is correct |
22 |
Correct |
213 ms |
23220 KB |
Output is correct |
23 |
Correct |
84 ms |
14752 KB |
Output is correct |
24 |
Correct |
222 ms |
23640 KB |
Output is correct |
25 |
Correct |
9 ms |
8792 KB |
Output is correct |
26 |
Correct |
3 ms |
7516 KB |
Output is correct |
27 |
Correct |
3 ms |
7516 KB |
Output is correct |
28 |
Correct |
13 ms |
10200 KB |
Output is correct |
29 |
Correct |
9 ms |
8796 KB |
Output is correct |
30 |
Correct |
3 ms |
7516 KB |
Output is correct |
31 |
Correct |
4 ms |
7516 KB |
Output is correct |
32 |
Correct |
4 ms |
7516 KB |
Output is correct |
33 |
Correct |
3 ms |
7768 KB |
Output is correct |
34 |
Correct |
7 ms |
8796 KB |
Output is correct |
35 |
Correct |
3 ms |
7516 KB |
Output is correct |
36 |
Correct |
3 ms |
7516 KB |
Output is correct |
37 |
Correct |
3 ms |
7516 KB |
Output is correct |
38 |
Correct |
3 ms |
7516 KB |
Output is correct |
39 |
Correct |
3 ms |
7516 KB |
Output is correct |
40 |
Correct |
230 ms |
24800 KB |
Output is correct |
41 |
Correct |
200 ms |
23932 KB |
Output is correct |
42 |
Correct |
223 ms |
24028 KB |
Output is correct |
43 |
Correct |
60 ms |
14672 KB |
Output is correct |
44 |
Correct |
59 ms |
14672 KB |
Output is correct |
45 |
Correct |
180 ms |
22808 KB |
Output is correct |
46 |
Correct |
185 ms |
22576 KB |
Output is correct |
47 |
Correct |
202 ms |
24716 KB |
Output is correct |
48 |
Correct |
65 ms |
14172 KB |
Output is correct |
49 |
Correct |
179 ms |
24536 KB |
Output is correct |
50 |
Correct |
235 ms |
22848 KB |
Output is correct |
51 |
Correct |
165 ms |
22820 KB |
Output is correct |