#include<bits/stdc++.h>
using namespace std;
#define int int64_t
#define all(x) x.begin(),x.end()
#define all1(x) x.rbegin(),x.rend()
#define sz(x) (int)(x.size())
const int N=1e4+5,N1=1e15,mod=1e9+7;
template<class T> using min_heap=priority_queue<T,vector<T>,greater<T>>;
void solve(){
int n,m,s,t,u,v;
cin>>n>>m>>s>>t>>u>>v;
using gh=pair<int,int>;
vector<gh> adj[n+1];
for (int i=1,x,y,w;i<=m;i++){
cin>>x>>y>>w;
adj[x].emplace_back(y,w);
adj[y].emplace_back(x,w);
}
vector<int> disu(n+1,N1),disv(n+1,N1);
min_heap<pair<int,int>> q;
q.emplace(0,u);
disu[u]=0;
while(!q.empty()){
int nd,dis;
tie(dis,nd)=q.top();
q.pop();
if (disu[nd]!=dis){continue;}
for (const pair<int,int> &it:adj[nd]){
if (disu[it.first]>dis+it.second){
disu[it.first]=dis+it.second;
q.emplace(disu[it.first],it.first);
}
}
}
disv[v]=0;
q.emplace(0,v);
while(!q.empty()){
int nd,dis;
tie(dis,nd)=q.top();
q.pop();
if (disv[nd]!=dis){continue;}
for (const pair<int,int> &it:adj[nd]){
if (disv[it.first]>dis+it.second){
disv[it.first]=dis+it.second;
q.emplace(disv[it.first],it.first);
}
}
}
vector<int> adj1[n+1];
vector<int> curdis(n+1,N1);
curdis[s]=0;
q.emplace(0,s);
vector<bool> curvis(n+1);
while(!q.empty()){
int nd,dis;
tie(dis,nd)=q.top();
q.pop();
for (const pair<int,int> &it:adj[nd]){
if (curdis[it.first]>dis+it.second){
curdis[it.first]=dis+it.second;
adj1[it.first].clear();
adj1[it.first].emplace_back(nd);
q.emplace(curdis[it.first],it.first);
}
else if (curdis[it.first]==dis+it.second){
adj1[it.first].emplace_back(nd);
}
}
}
vector<int> adj2[n+1];
fill(all(curvis),false);
queue<int> q1;
q1.emplace(t);
while(!q1.empty()){
int nd=q1.front();
q1.pop();
if (!curvis[nd]){
curvis[nd]=1;
for (int it:adj1[nd]){
adj2[it].emplace_back(nd);
q1.emplace(it);
}
}
}
vector<int> adj3[n+1];
for (int i=1;i<=n;i++){
for (int it:adj2[i]){
adj3[it].emplace_back(i);
}
}
vector<int> indeg1(n+1),indeg2(n+1);
for (int i=1;i<=n;i++){
for (int it:adj2[i]){
indeg1[it]++;
}
}
for (int i=1;i<=n;i++){
if (!indeg1[i]){
q1.emplace(i);
}
}
vector<int> forwarddp(n+1),backwardp(n+1);
for (int i=1;i<=n;i++){
forwarddp[i]=backwardp[i]=disv[i];
}
while(!q1.empty()){
int nd=q1.front();
q1.pop();
for (const int &it:adj2[nd]){
indeg1[it]--;
forwarddp[it]=min(forwarddp[it],forwarddp[nd]);
if (indeg1[it]==0){q1.emplace(it);}
}
}
for (int i=1;i<=n;i++){
for (int it:adj3[i]){
indeg2[it]++;
}
}
for (int i=1;i<=n;i++){
if (indeg2[i]==0){q1.emplace(i);}
}
while(!q1.empty()){
int nd=q1.front();
q1.pop();
for (const int &it:adj3[nd]){
indeg2[it]--;
backwardp[it]=min(backwardp[it],backwardp[nd]);
if (indeg2[it]==0){q1.emplace(it);}
}
}
assert(*max_element(all(indeg1))<=0);
assert(1);
int ans=disu[v];
for (int i=1;i<=n;i++){
if (!curvis[i]){continue;}
ans=min(ans,disu[i]+min(forwarddp[i],backwardp[i]));
}
cout<<ans;
}
int32_t main(){
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
int tq=1;
//cin>>tq;
for (;tq;tq--){solve();}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
273 ms |
33356 KB |
Output is correct |
2 |
Correct |
287 ms |
34896 KB |
Output is correct |
3 |
Correct |
305 ms |
36532 KB |
Output is correct |
4 |
Correct |
289 ms |
33508 KB |
Output is correct |
5 |
Correct |
339 ms |
36064 KB |
Output is correct |
6 |
Correct |
293 ms |
33448 KB |
Output is correct |
7 |
Correct |
313 ms |
36600 KB |
Output is correct |
8 |
Correct |
301 ms |
36184 KB |
Output is correct |
9 |
Correct |
280 ms |
32840 KB |
Output is correct |
10 |
Correct |
238 ms |
32668 KB |
Output is correct |
11 |
Correct |
148 ms |
28348 KB |
Output is correct |
12 |
Correct |
268 ms |
33068 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
310 ms |
34664 KB |
Output is correct |
2 |
Correct |
330 ms |
34916 KB |
Output is correct |
3 |
Correct |
325 ms |
34484 KB |
Output is correct |
4 |
Correct |
303 ms |
34696 KB |
Output is correct |
5 |
Correct |
330 ms |
35152 KB |
Output is correct |
6 |
Correct |
290 ms |
36260 KB |
Output is correct |
7 |
Correct |
352 ms |
36760 KB |
Output is correct |
8 |
Correct |
333 ms |
34860 KB |
Output is correct |
9 |
Correct |
328 ms |
35256 KB |
Output is correct |
10 |
Correct |
364 ms |
34616 KB |
Output is correct |
11 |
Correct |
169 ms |
29512 KB |
Output is correct |
12 |
Correct |
301 ms |
36416 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
2308 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
312 KB |
Output is correct |
4 |
Correct |
15 ms |
3888 KB |
Output is correct |
5 |
Correct |
8 ms |
1952 KB |
Output is correct |
6 |
Correct |
1 ms |
460 KB |
Output is correct |
7 |
Correct |
2 ms |
488 KB |
Output is correct |
8 |
Correct |
2 ms |
532 KB |
Output is correct |
9 |
Correct |
1 ms |
460 KB |
Output is correct |
10 |
Correct |
7 ms |
1968 KB |
Output is correct |
11 |
Correct |
1 ms |
308 KB |
Output is correct |
12 |
Correct |
1 ms |
324 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
320 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
273 ms |
33356 KB |
Output is correct |
2 |
Correct |
287 ms |
34896 KB |
Output is correct |
3 |
Correct |
305 ms |
36532 KB |
Output is correct |
4 |
Correct |
289 ms |
33508 KB |
Output is correct |
5 |
Correct |
339 ms |
36064 KB |
Output is correct |
6 |
Correct |
293 ms |
33448 KB |
Output is correct |
7 |
Correct |
313 ms |
36600 KB |
Output is correct |
8 |
Correct |
301 ms |
36184 KB |
Output is correct |
9 |
Correct |
280 ms |
32840 KB |
Output is correct |
10 |
Correct |
238 ms |
32668 KB |
Output is correct |
11 |
Correct |
148 ms |
28348 KB |
Output is correct |
12 |
Correct |
268 ms |
33068 KB |
Output is correct |
13 |
Correct |
310 ms |
34664 KB |
Output is correct |
14 |
Correct |
330 ms |
34916 KB |
Output is correct |
15 |
Correct |
325 ms |
34484 KB |
Output is correct |
16 |
Correct |
303 ms |
34696 KB |
Output is correct |
17 |
Correct |
330 ms |
35152 KB |
Output is correct |
18 |
Correct |
290 ms |
36260 KB |
Output is correct |
19 |
Correct |
352 ms |
36760 KB |
Output is correct |
20 |
Correct |
333 ms |
34860 KB |
Output is correct |
21 |
Correct |
328 ms |
35256 KB |
Output is correct |
22 |
Correct |
364 ms |
34616 KB |
Output is correct |
23 |
Correct |
169 ms |
29512 KB |
Output is correct |
24 |
Correct |
301 ms |
36416 KB |
Output is correct |
25 |
Correct |
8 ms |
2308 KB |
Output is correct |
26 |
Correct |
1 ms |
332 KB |
Output is correct |
27 |
Correct |
1 ms |
312 KB |
Output is correct |
28 |
Correct |
15 ms |
3888 KB |
Output is correct |
29 |
Correct |
8 ms |
1952 KB |
Output is correct |
30 |
Correct |
1 ms |
460 KB |
Output is correct |
31 |
Correct |
2 ms |
488 KB |
Output is correct |
32 |
Correct |
2 ms |
532 KB |
Output is correct |
33 |
Correct |
1 ms |
460 KB |
Output is correct |
34 |
Correct |
7 ms |
1968 KB |
Output is correct |
35 |
Correct |
1 ms |
308 KB |
Output is correct |
36 |
Correct |
1 ms |
324 KB |
Output is correct |
37 |
Correct |
1 ms |
332 KB |
Output is correct |
38 |
Correct |
1 ms |
332 KB |
Output is correct |
39 |
Correct |
1 ms |
320 KB |
Output is correct |
40 |
Correct |
259 ms |
32700 KB |
Output is correct |
41 |
Correct |
255 ms |
32264 KB |
Output is correct |
42 |
Correct |
256 ms |
31104 KB |
Output is correct |
43 |
Correct |
149 ms |
30544 KB |
Output is correct |
44 |
Correct |
170 ms |
30136 KB |
Output is correct |
45 |
Correct |
376 ms |
37076 KB |
Output is correct |
46 |
Correct |
341 ms |
37100 KB |
Output is correct |
47 |
Correct |
287 ms |
31160 KB |
Output is correct |
48 |
Correct |
195 ms |
30276 KB |
Output is correct |
49 |
Correct |
239 ms |
31396 KB |
Output is correct |
50 |
Correct |
337 ms |
35832 KB |
Output is correct |
51 |
Correct |
394 ms |
37048 KB |
Output is correct |