#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int MAXN = 1e5; const ll INF = 1e18; int N, M, S, T, U, V; ll DU[MAXN+10], DV[MAXN+10], DS[MAXN+10], dp[MAXN+10][2]; vector<pll> adj[MAXN+10]; vector<int> adj2[MAXN+10], revadj2[MAXN+10]; struct Queue { ll v, w; bool operator < (const Queue& p) const { return w>p.w; } }; void dijk(int s, ll* D) { int i, j; for(i=1; i<=N; i++) D[i]=INF; priority_queue<Queue> PQ; PQ.push({s, 0}); while(!PQ.empty()) { Queue T=PQ.top(); PQ.pop(); if(D[T.v]<=T.w) continue; D[T.v]=T.w; for(pii nxt : adj[T.v]) { PQ.push({nxt.first, nxt.second+T.w}); } } } bool vis[MAXN+10]; vector<int> order; void dfs(int now) { vis[now]=true; for(int nxt : adj2[now]) if(!vis[nxt]) dfs(nxt); order.push_back(now); } int main() { int i, j; scanf("%d%d%d%d%d%d", &N, &M, &S, &T, &U, &V); for(i=1; i<=M; i++) { int u, v, w; scanf("%d%d%d", &u, &v, &w); adj[u].push_back({v, w}); adj[v].push_back({u, w}); } dijk(U, DU); dijk(V, DV); dijk(S, DS); for(i=1; i<=N; i++) { for(pll nxt : adj[i]) if(DS[i]+nxt.second==DS[nxt.first]) { adj2[i].push_back(nxt.first); revadj2[nxt.first].push_back(i); //printf("%d ", nxt); } } //for(i=1; i<=N; i++) printf("U : %lld / V : %lld / S : %lld\n", DU[i], DV[i], DS[i]); dfs(S); reverse(order.begin(), order.end()); for(int now : order) { dp[now][0]=INF; dp[now][1]=INF; for(int nxt : revadj2[now]) { if(min(dp[nxt][0], DU[now])+min(dp[nxt][1], DV[now])<dp[now][0]+dp[now][1]) { dp[now][0]=min(dp[nxt][0], DU[now]); dp[now][1]=min(dp[nxt][1], DV[now]); } } dp[now][0]=min(dp[now][0], DU[now]); dp[now][1]=min(dp[now][1], DV[now]); //printf("%d %lld %lld\n", now, dp[now][0], dp[now][1]); } printf("%lld", min(dp[T][0]+dp[T][1], DU[V])); }

commuter_pass.cpp: In function 'void dijk(int, ll*)':
commuter_pass.cpp:24:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:52:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
commuter_pass.cpp:54:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d%d%d%d", &N, &M, &S, &T, &U, &V);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:58:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &u, &v, &w);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~