// 23 - 12 - 23
#include<bits/stdc++.h>
using namespace std;
#define read() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define day() time_t now = time(0);char* x = ctime(&now);cerr<<"Right Now Is : "<<x<<"\n"
#define int long long
#define ii pair<int,int>
#define X first
#define Y second
const long long MAX = (int)3e5 + 5;
const long long INF = (int)1e18;
const long long MOD = (int)1e9 + 7;
int n,m;
vector<ii> adj[MAX];
int s,t,ux,vx;
vector<int> g[MAX];
int dist[MAX][3];
priority_queue<ii,vector<ii>,greater<ii>> q;
bool dd[MAX];
int res = INF;
int dp[MAX][3];
void calc(int u,int p,int x,int y){
dp[u][x] = min(dist[u][x],dp[u][x]);
for(auto v : g[u]){
if(v == p)assert(v == p);
dp[v][x] = dp[u][x];
calc(v,u,x,y);
}
res = min(res,dp[u][x] + dist[u][y]);
}
void dijsktra(int st,int ct){
for(int i = 1;i <= n;i++)dist[i][ct] = INF;
q.push({0,st});
dist[st][ct] = 0;
while(!q.empty()){
int u = q.top().Y;
int c = q.top().X;
q.pop();
if(c != dist[u][ct])continue;
for(auto e : adj[u]){
int v = e.X;
int w = e.Y;
if(dist[v][ct] > dist[u][ct] + w){
dist[v][ct] = dist[u][ct] + w;
q.push({dist[v][ct],v});
}
}
}
}
signed main(){
cin >> n >> m >> s >> t >> ux >> vx;
for(int i = 1,u,v,w;i <= m;i++){
cin >> u >> v >> w;
adj[u].push_back({v,w});
adj[v].push_back({u,w});
}
dijsktra(s,0);
deque<int> h;
h.push_back(t);
dd[t] = 1;
while(!h.empty()){
int u = h.front();
h.pop_front();
for(auto e : adj[u]){
if(dist[u][0] == dist[e.X][0] + e.Y){
if(!dd[e.X]){
dd[e.X] = 1;
h.push_back(e.X);
}
g[e.X].push_back(u);
}
}
}
dijsktra(ux,1);
dijsktra(vx,2);
for(int i = 1;i <= n;i++){
for(int j = 0;j < 3;j++){
dp[i][j] = INF;
}
}
res = min({res,dist[ux][2],dist[vx][1]});
// calc(s,0,1,2);
// calc(s,0,2,1);
cout << res;
}
# | 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... |