CUBE-T196: Royal Parade

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

typedef long long lli;
typedef pair<int, int> pii;
typedef pair<lli, int> pli;

const int N = 1e5;

vector<pii> adj[N + 1];
int nVertex;
lli dist[2][N + 1];
bool visited[N + 1], royal[N + 1];

void dijkstra(int i, int st){
    for(int u = 1; u <= nVertex; ++u){
        dist[i][u] = 1e18;
        visited[u] = false;
    }
    priority_queue<pli, vector<pli>, greater<pli>> pq;
    dist[i][st] = 0;
    pq.emplace(dist[i][st], st);
    while(!pq.empty()){
        int u = pq.top().second;
        pq.pop();
        if(visited[u]){
            continue;
        }
        visited[u] = true;
        for(pii p : adj[u]){
            int v = p.first;
            int w = p.second;
            if(!visited[v] && dist[i][u] + w < dist[i][v]){
                dist[i][v] = dist[i][u] + w;
                pq.emplace(dist[i][v], v);
            }
        }
    }
}

int main(){

    int nEdge;
    scanf("%d%d", &nVertex, &nEdge);
    for(int i = 1; i <= nEdge; ++i){
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }
    int royalSt, royalEd, st, ed;
    scanf("%d%d%d%d", &royalSt, &royalEd, &st, &ed);
    dijkstra(0, royalSt);
    dijkstra(1, royalEd);

    lli stPath = dist[0][royalEd];
    for(int i = 1; i <= nVertex; ++i){
        if(dist[0][i] + dist[1][i] == stPath){
            royal[i] = true;
        }
    }

    for(int i = 1; i <= nVertex; ++i){
        dist[0][i] = 1e18;
        visited[i] = false;
    }
    priority_queue<pli, vector<pli>, greater<pli>> pq;
    if(!royal[st]){
        dist[0][st] = 0;
        pq.emplace(dist[0][st], st);
    }
    while(!pq.empty()){
        int u = pq.top().second;
        pq.pop();
        if(visited[u]){
            continue;
        }
        if(u == ed){
            cout << dist[0][ed];
            return 0;
        }
        visited[u] = true;
        for(pii p : adj[u]){
            int v = p.first;
            int w = p.second;
            if(!royal[v] && !visited[v] && dist[0][u] + w < dist[0][v]){
                dist[0][v] = dist[0][u] + w;
                pq.emplace(dist[0][v], v);
            }
        }
    }
    cout << "-1";

    return 0;
}