TUMSO18: Zombie Land

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

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

const int N = 2e5;

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

void dijkstra(int i, int st){
    for(int u = 1; u <= nVertex; ++u){
        visited[u] = false;
        dist[i][u] = 1e18;
    }
    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, st, ed;
    scanf("%d%d%d%d", &nVertex, &nEdge, &st, &ed);
    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);
    }
    dijkstra(0, st);
    dijkstra(1, ed);
    priority_queue<pli, vector<pli>, greater<pli>> pq;
    for(int i = 1; i <= nVertex; ++i){
        dist2[i] = 1e18;
        visited[i] = false;
    }
    lli stPath = dist[0][ed];
    for(int i = 1; i <= nVertex; ++i){
        if(dist[0][i] + dist[1][i] == stPath){
            dist2[i] = 0;
            pq.emplace(dist2[i], i);
        }
    }
    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] && dist2[u] + w < dist2[v]){
                dist2[v] = dist2[u] + w;
                pq.emplace(dist2[v], v);
            }
        }
    }
    int Q;
    scanf("%d", &Q);
    while(Q--){
        int u;
        scanf("%d", &u);
        cout << dist2[u] << '\n';
    }

    return 0;
}