//#pragma GCC optimize("O3,unroll-loops,Ofast")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
//#define endl "\n"
#define F first
#define S second
#define pb push_back
#define pf push_front
#define popf pop_frot
#define popb pop_back
#define int long long
#define in insert
//#define mid (l+r)/2
//register int cnt
using namespace std;
const int N=1e5+5;
int n,m,S,T,U,V,dp[N][4][2],dis[5][N],vis[N],k=0;
vector<pair<int,int>> adj[N];
vector<int> E[N][2];
void calc(int G){
++k;
for(int i=1;i<=n;i++) vis[i]=0;
for(int i=1;i<=n;i++) dis[k][i]=1e17;
dis[k][G]=0;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
q.push({0,G});
while(!q.empty()){
int node=q.top().S,d=q.top().F;
q.pop();
if(vis[node]) continue ;
vis[node]=1;
for(auto u : adj[node]){
if(dis[k][u.F]>u.S+d){
dis[k][u.F]=u.S+d;
q.push({dis[k][u.F],u.F});
}
}
}
return ;
}
int rec(int node , int type , int t){
if(dp[node][type][t]!=-1) return dp[node][type][t];
int ret=dis[type][node];
for(auto u : E[node][t]){
ret=min(ret,rec(u,type,t));
}
return dp[node][type][t]=ret;
}
int32_t main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(nullptr);
memset(dp,-1,sizeof dp);
cin>>n>>m;
cin>>S>>T;
cin>>U>>V;
for(int i=1;i<=m;i++){
int x,y,z;cin>>x>>y>>z;
adj[x].pb({y,z});
adj[y].pb({x,z});
}
calc(S);
calc(U);
calc(V);
calc(T);
memset(vis,0,sizeof vis);
queue<int> q;
q.push(S);
while(!q.empty()){
int node=q.front();
q.pop();
vis[node]=1;
for(auto u : adj[node]){
if(dis[1][u.F]==u.S+dis[1][node] && dis[1][u.F]+dis[4][u.F]==dis[1][T] && vis[u.F]==0){
E[node][0].pb(u.F);
E[u.F][1].pb(node);
vis[u.F]=1;
q.push(u.F);
}
}
}
int ret=dis[2][V];
for(int i=1;i<=n;i++){
if(vis[i]){
ret=min({ret,dis[2][i]+rec(i,3,0),dis[2][i]+rec(i,3,1)});
}
}
cout<<ret;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |