CUBE-196: Royal Parade

#include <bits/stdc++.h>
using namespace std;

using lli = long long;
const lli INF = 2e18;
using pil = pair <int, lli>;
using pli = pair <lli, int>;
int n, m, A, B, C, D;
vector <pil> g[100001];
vector < vector <lli>> dis(3, vector <lli> (100001, INF));

lli find_distance(int start, int opr){

    vector <int> visited(n + 1, false);
    priority_queue <pli, vector <pli>, greater <pli>> pq;
    pq.push({0, start});
    dis[opr][start] = 0;

    while(pq.size() > 0){
        lli d = pq.top().first;
        int u = pq.top().second;
        pq.pop();

        if(visited[u])
            continue;
        visited[u] = true;

        if(opr == 2 and u == D) return d;

        for(auto vw: g[u]){
            int v = vw.first;
            lli w = vw.second;
            if(opr == 2){
                if(dis[0][v] + dis[1][v] != dis[0][B]){
                    dis[opr][v] = d + w;
                    pq.push({dis[opr][v], v});
                }
                continue;
            }
            if(!visited[v] and d + w < dis[opr][v]){
                dis[opr][v] = d + w;
                pq.push({dis[opr][v], v});
            }
        }
    }
    return -1;
}

int main(){

    scanf("%d%d", &n, &m);

    for(int i = 1; i <= m; i++){
        int u, v;
        lli w;
        scanf("%d%d%lld", &u, &v, &w);
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }

    scanf("%d%d%d%d", &A, &B, &C, &D);

    find_distance(A, 0);
    find_distance(B, 1);

    printf("%lld",find_distance(C, 2));

    return 0;
}