# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1182650 | elotelo966 | Commuter Pass (JOI18_commuter_pass) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define OYY LLONG_MAX
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define fi first
#define se second
#define FOR for(int i=1;i<=n;i++)
#define mid (start+end)/2
#define pb push_back
#define lim 100005
const int mod=1000000007;
int n,m,s,t,u,v;
vector<pair<int,int>> adj[lim];
vector<int> ne[lim];
int vis[lim],dist[lim][4],dp[lim];
inline void dij(int bas_node,int kim){
FOR{
vis[i]=0;
dist[i][kim]=OYY;
}
dist[bas_node][kim]=0;
priority_queue<pair<int,int>> pq;
pq.push({0,bas_node});
while(pq.size()){
int node=pq.top().se;
pq.pop();
if(vis[node])continue;
vis[node]=1;
for(auto go:adj[node]){
if(dist[node][kim]!=OYY && dist[node][kim]+go.se<dist[go.fi][kim]){
dist[go.fi][kim]=dist[node][kim]+go.se;
pq.push({-dist[go.fi][kim],go.fi});
}
}
}
}
inline bool check(int node1,int node2,int cost){
if(dist[
}
inline void cal(){
FOR{
vis[i]=0;
}
queue<int> q;
q.push(s);
while(q.size()){
int cur_node=q.front();
q.pop();
if(vis[cur_node])continue;
vis[cur_node]=1;
for(auto go:adj[cur_node]){
if(check(node,go.fi,go.se)){
ne[node].pb(go.fi);
q.push(go.fi);
}
}
}
}
int32_t main(){
faster
cin>>n>>m;
cin>>s>>t>>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});
}
dij(s,0);
dij(u,1);
dij(v,2);
dij(t,3);
cal();
int cev=dist[v][1];
FOR{
cev=min(cev,dist[i][1]+dp[i]);
}
cout<<cev<<'\n';
return 0;
}