#include <bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define FOR(i,l,r,d) for(int i=(l);i<=(r);i+=(d))
#define vi vector<int>
#define pii pair<int,int>
#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define mkp make_pair
const int INF=2147483647;
const int MOD=1000000007;
const int mod=998244353;
const double eps=1e-12;
int n,m;
int S,T,U,V;
vector<pii> edge[100001];
bool vis[100001];
int ds[100001],du[100001],dv[100001];
vi spt[100001];
int res;
void Dijkstra(int from,int dis[]){
priority_queue< pii, vector<pii>, greater<pii> > pq;
FOR(i,0,n-1,1){
dis[i] = INF*INF;
vis[i] = 0;
}
dis[from] = 0;
pq.emplace(0,from);
while( !pq.empty() ){
int cdis = pq.top().F;
int v = pq.top().S;
pq.pop();
if( cdis != dis[v] ){
continue;
}
vis[v] = 1;
for(pii i : edge[v]){
if( dis[v]+i.S < dis[i.F] ){
dis[i.F] = dis[v]+i.S;
pq.emplace(dis[i.F],i.F);
}
}
}
}
int indeg[100001];
int dpu[100001],dpv[100001];
vi qu;
vi dporder;
void solve(){
FOR(i,0,n-1,1){
indeg[i] = 0;
}
FOR(i,0,n-1,1){
for(int j : spt[i]){
indeg[j]++;
}
}
FOR(i,0,n-1,1){
if(indeg[i]==0){
qu.pb(i);
}
}
while( !qu.empty() ){
int v = qu.back();
qu.pop_back();
dporder.pb(v);
for(int i : spt[v]){
indeg[i]--;
if(indeg[i]==0){
qu.pb(i);
}
}
}
FOR(i,0,n-1,1){
dpu[i] = du[i];
dpv[i] = dv[i];
}
for(int i : dporder){
for(int j : spt[i]){
if( min( dpu[i] , du[j] ) + min( dpv[i] , dv[j] ) < dpu[j] + dpv[j] ){
dpu[j] = min( dpu[i] , du[j] );
dpv[j] = min( dpv[i] , dv[j] );
}
}
}
/*
cerr<<"dpu : ";
FOR(i,0,n-1,1){
if(dpu[i]>100) cerr<<"- ";
else cerr<<dpu[i]<<" ";
}
cerr<<endl;
cerr<<"dpv : ";
FOR(i,0,n-1,1){
if(dpv[i]>100) cerr<<"- ";
else cerr<<dpv[i]<<" ";
}
cerr<<endl;
*/
res = min( res , dpu[T] + dpv[T] );
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m>>S>>T>>U>>V;
S--;
T--;
U--;
V--;
FOR(i,0,m-1,1){
int v1,v2,w;
cin>>v1>>v2>>w;
v1--;
v2--;
edge[v1].eb(v2,w);
edge[v2].eb(v1,w);
}
Dijkstra(S,ds);
Dijkstra(U,du);
Dijkstra(V,dv);
/*
cerr<<"ds : ";
FOR(i,0,n-1,1){
cerr<<ds[i]<<" ";
}
cerr<<endl;
cerr<<"du : ";
FOR(i,0,n-1,1){
cerr<<du[i]<<" ";
}
cerr<<endl;
cerr<<"dv : ";
FOR(i,0,n-1,1){
cerr<<dv[i]<<" ";
}
cerr<<endl;
*/
res = du[V];
vi sptqu;
bool inqu[100001];
FOR(i,0,n-1,1){
inqu[i] = 0;
}
sptqu.pb(T);
inqu[T] = 1;
int cnt = 0;
while( !sptqu.empty() ){
int v = sptqu.back();
sptqu.pop_back();
for(pii i : edge[v]){
if( ds[i.F] + i.S == ds[v] ){
spt[i.F].pb(v);
if( inqu[i.F] == 0 ){
inqu[i.F] = 1;
sptqu.pb(i.F);
}
}
}
cnt++;
assert(cnt <= max(n,m)*10);
}
/*
cerr<<"spt : "<<endl;
FOR(i,0,n-1,1){
cerr<<"spt["<<i<<"] : ";
for(int j : spt[i]){
cerr<<j<<" ";
}
cerr<<endl;
}
cerr<<endl;
*/
solve();
swap(U,V);
FOR(i,0,n-1,1){
swap(du[i],dv[i]);
}
solve();
cout<<res<<endl;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
325 ms |
24772 KB |
Output is correct |
2 |
Correct |
346 ms |
24816 KB |
Output is correct |
3 |
Correct |
354 ms |
29268 KB |
Output is correct |
4 |
Correct |
301 ms |
28596 KB |
Output is correct |
5 |
Correct |
376 ms |
28664 KB |
Output is correct |
6 |
Correct |
349 ms |
28472 KB |
Output is correct |
7 |
Correct |
394 ms |
28892 KB |
Output is correct |
8 |
Correct |
423 ms |
29092 KB |
Output is correct |
9 |
Correct |
318 ms |
29164 KB |
Output is correct |
10 |
Correct |
276 ms |
29144 KB |
Output is correct |
11 |
Correct |
181 ms |
20984 KB |
Output is correct |
12 |
Correct |
363 ms |
29052 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
353 ms |
24856 KB |
Output is correct |
2 |
Correct |
366 ms |
24792 KB |
Output is correct |
3 |
Correct |
358 ms |
24664 KB |
Output is correct |
4 |
Correct |
359 ms |
24792 KB |
Output is correct |
5 |
Correct |
366 ms |
24944 KB |
Output is correct |
6 |
Correct |
373 ms |
25600 KB |
Output is correct |
7 |
Correct |
382 ms |
25704 KB |
Output is correct |
8 |
Correct |
354 ms |
24792 KB |
Output is correct |
9 |
Correct |
375 ms |
24900 KB |
Output is correct |
10 |
Correct |
351 ms |
24664 KB |
Output is correct |
11 |
Correct |
176 ms |
19436 KB |
Output is correct |
12 |
Correct |
375 ms |
25668 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
6508 KB |
Output is correct |
2 |
Correct |
4 ms |
5100 KB |
Output is correct |
3 |
Correct |
5 ms |
5100 KB |
Output is correct |
4 |
Correct |
20 ms |
8556 KB |
Output is correct |
5 |
Correct |
12 ms |
6892 KB |
Output is correct |
6 |
Correct |
4 ms |
5228 KB |
Output is correct |
7 |
Correct |
5 ms |
5228 KB |
Output is correct |
8 |
Correct |
5 ms |
5356 KB |
Output is correct |
9 |
Correct |
5 ms |
5228 KB |
Output is correct |
10 |
Correct |
12 ms |
6892 KB |
Output is correct |
11 |
Correct |
4 ms |
5100 KB |
Output is correct |
12 |
Correct |
4 ms |
5120 KB |
Output is correct |
13 |
Correct |
4 ms |
5100 KB |
Output is correct |
14 |
Correct |
4 ms |
5228 KB |
Output is correct |
15 |
Correct |
4 ms |
5228 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
325 ms |
24772 KB |
Output is correct |
2 |
Correct |
346 ms |
24816 KB |
Output is correct |
3 |
Correct |
354 ms |
29268 KB |
Output is correct |
4 |
Correct |
301 ms |
28596 KB |
Output is correct |
5 |
Correct |
376 ms |
28664 KB |
Output is correct |
6 |
Correct |
349 ms |
28472 KB |
Output is correct |
7 |
Correct |
394 ms |
28892 KB |
Output is correct |
8 |
Correct |
423 ms |
29092 KB |
Output is correct |
9 |
Correct |
318 ms |
29164 KB |
Output is correct |
10 |
Correct |
276 ms |
29144 KB |
Output is correct |
11 |
Correct |
181 ms |
20984 KB |
Output is correct |
12 |
Correct |
363 ms |
29052 KB |
Output is correct |
13 |
Correct |
353 ms |
24856 KB |
Output is correct |
14 |
Correct |
366 ms |
24792 KB |
Output is correct |
15 |
Correct |
358 ms |
24664 KB |
Output is correct |
16 |
Correct |
359 ms |
24792 KB |
Output is correct |
17 |
Correct |
366 ms |
24944 KB |
Output is correct |
18 |
Correct |
373 ms |
25600 KB |
Output is correct |
19 |
Correct |
382 ms |
25704 KB |
Output is correct |
20 |
Correct |
354 ms |
24792 KB |
Output is correct |
21 |
Correct |
375 ms |
24900 KB |
Output is correct |
22 |
Correct |
351 ms |
24664 KB |
Output is correct |
23 |
Correct |
176 ms |
19436 KB |
Output is correct |
24 |
Correct |
375 ms |
25668 KB |
Output is correct |
25 |
Correct |
12 ms |
6508 KB |
Output is correct |
26 |
Correct |
4 ms |
5100 KB |
Output is correct |
27 |
Correct |
5 ms |
5100 KB |
Output is correct |
28 |
Correct |
20 ms |
8556 KB |
Output is correct |
29 |
Correct |
12 ms |
6892 KB |
Output is correct |
30 |
Correct |
4 ms |
5228 KB |
Output is correct |
31 |
Correct |
5 ms |
5228 KB |
Output is correct |
32 |
Correct |
5 ms |
5356 KB |
Output is correct |
33 |
Correct |
5 ms |
5228 KB |
Output is correct |
34 |
Correct |
12 ms |
6892 KB |
Output is correct |
35 |
Correct |
4 ms |
5100 KB |
Output is correct |
36 |
Correct |
4 ms |
5120 KB |
Output is correct |
37 |
Correct |
4 ms |
5100 KB |
Output is correct |
38 |
Correct |
4 ms |
5228 KB |
Output is correct |
39 |
Correct |
4 ms |
5228 KB |
Output is correct |
40 |
Correct |
296 ms |
28020 KB |
Output is correct |
41 |
Correct |
316 ms |
29088 KB |
Output is correct |
42 |
Correct |
324 ms |
29032 KB |
Output is correct |
43 |
Correct |
230 ms |
22372 KB |
Output is correct |
44 |
Correct |
223 ms |
22500 KB |
Output is correct |
45 |
Correct |
501 ms |
29748 KB |
Output is correct |
46 |
Correct |
412 ms |
29492 KB |
Output is correct |
47 |
Correct |
329 ms |
28788 KB |
Output is correct |
48 |
Correct |
226 ms |
21736 KB |
Output is correct |
49 |
Correct |
256 ms |
27644 KB |
Output is correct |
50 |
Correct |
468 ms |
29868 KB |
Output is correct |
51 |
Correct |
416 ms |
29628 KB |
Output is correct |