#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define lc 2*pos
#define rc 2*pos+1
#define pii pair<int,int>
#define fi first
#define se second
//CEK ENDL DAN INT LL
#define endl '\n'
#define inf 1e18
#define ti tuple<int,int,int>
#define meekucaon ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int mod=1e9+7;
int sf(int a){return (a%mod+mod)%mod;}
int kal(int a,int b){return (sf(a)*sf(b))%mod;}
int tam(int a,int b){return (sf(a)+sf(b))%mod;}
int kur(int a,int b){return (sf(a)+mod-sf(b))%mod;}
int inv(int a){
if(a<=1) return 1;
return mod-(int)(mod/a)*inv(mod%a)%mod;
}
int bag(int a,int b){return kal(sf(a),inv(b));}
const int lim=100000;
int dis[5][lim+10];
vector<pii>g[lim+10];
int n,m,s,t,a,b;
int nodso(int u,int v,int w){
if((dis[0][u]+w==dis[0][v]) && (dis[1][u]==dis[1][v]+w) && dis[1][u]+dis[1][v]+w==dis[0][t]) return 1;
if((dis[0][v]+w==dis[0][u])&& (dis[1][v]==dis[1][u]+w) && dis[0][u]+dis[0][v]+w==dis[0][t]) return 1;
return 0;
}
void dji(int ta,int st){
priority_queue<pii,vector<pii>,greater<pii>>q;
q.push({0,st});
dis[ta][st]=0;
while(q.size()){
auto [d,u]=q.top();
q.pop();
if(dis[ta][u]<d) continue;
for(auto [v,w]:g[u]){
if(dis[ta][u]+w>=dis[ta][v]) continue;
dis[ta][v]=dis[ta][u]+w;
q.push({dis[ta][v],v});
}
}
}
int vis[lim+10];
signed main(){
meekucaon
cin>>n>>m>>s>>t>>a>>b;
int dp[2][n+10];
for(int i=1;i<=n;i++){
dp[0][i]=inf;
dp[1][i]=inf;
for(int j=0;j<4;j++){
dis[j][i]=inf;
}
}
for(int i=1;i<=m;i++){
int u,v,w;cin>>u>>v>>w;
g[u].pb({v,w});
g[v].pb({u,w});
}
dji(0,s);dji(1,t);dji(2,a);dji(3,b);
queue<int>q;
q.push(s);
int ans=dis[3][a];
while(q.size()){
int u=q.front();
q.pop();
vis[u]=1;
dp[0][u]=min(dp[0][u],dis[2][u]);
dp[1][u]=min(dp[1][u],dis[3][u]);
ans=min(ans,dp[0][u]+dp[1][u]);
for(auto [v,w]:g[u]){
if(nodso(u,v,w)){
vis[v]=1;
dp[0][v]=min(dp[0][u],dp[0][v]);
dp[1][v]=min(dp[1][u],dp[1][v]);
if(!vis[v])q.push(v);
}
}
}
cout<<ans;
}
// 1. pasti dp
// obs
// 1. kalau masuk dalam shortest path bebas masuk keluar mana aja
// 2. save smallest dari suatu node ke s,t,a,b
// // subsoal
// // (1 & 2)
// // kalau masi masuk shortest path = 0
// // (3)
// // N<=300
// // tiap shortest route x all
// subtask 3
// n*n*n cek apakah ij dalam satu lane if yes then take min
// how to make it in m/n
# | 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... |