TUMSO18-C: Zombie Land

#include <bits/stdc++.h>

using namespace std;
using lli = long long;
const lli INF = 1e18;
const int N = 2e5 + 10;
using pl = pair <lli, lli>;
vector <pl> g[N];
lli disS[N], disE[N], disAns[N];
bool vsS[N], vsE[N], danger[N], vsAns[N];
lli n, m, S, E, Q;

void FindS(){
    for(lli i=0;i<=n;i++) disS[i] = INF, vsS[i] = false;
    priority_queue <pl, vector <pl>, greater <pl>> pq;
    disS[S] = 0;
    pq.push({ disS[S] , S });
    while(!pq.empty()){
        lli d = pq.top().first, u = pq.top().second; pq.pop();
        if(vsS[u]) continue; vsS[u] = true;
        for(auto vw: g[u]){
            lli v = vw.first, w = vw.second;
            if(!vsS[v] and d + w < disS[v]){
                disS[v] = d + w;
                pq.push({disS[v], v});
            }
        }
    }
}

void FindE(){
    for(lli i=0;i<=n;i++) disE[i] = INF, vsE[i] = false;
    priority_queue <pl, vector <pl>, greater <pl>> pq;
    disE[E] = 0;
    pq.push({ disE[E] , E });
    while(!pq.empty()){
        lli d = pq.top().first, u = pq.top().second; pq.pop();
        if(vsE[u]) continue; vsE[u] = true;
        for(auto vw: g[u]){
            lli v = vw.first, w = vw.second;
            if(!vsE[v] and d + w < disE[v]){
                disE[v] = d + w;
                pq.push({disE[v], v});
            }
        }
    }
}

void FindAns(lli stp){
    for(lli i=0;i<=n;i++) disAns[i] = INF, vsAns[i] = false;
    priority_queue <pl, vector <pl>, greater <pl>> pq;
    for(lli i=1;i<=n;i++){
        if(disS[i] + disE[i] == stp){
            danger[i] = true;
            disAns[i] = 0;
            pq.push({disAns[i], i});
        }
    }
    while(!pq.empty()){
        lli d = pq.top().first, u = pq.top().second; pq.pop();
        if(vsAns[u]) continue; vsAns[u] = true;
        for(auto vw: g[u]){
            lli v = vw.first, w = vw.second;
            if(!vsAns[v] and d + w < disAns[v]){
                disAns[v] = d + w;
                pq.push({disAns[v], v});
            }
        }
    }
}

int main(){

    scanf("%lld%lld%lld%lld", &n, &m, &S, &E);

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

    FindS();
    FindE();
    lli stp = disS[E];

    FindAns(stp);

    scanf("%lld", &Q);

    for(lli q=1;q<=Q;q++){
        lli u;
        scanf("%lld", &u);
        printf("%lld\n", disAns[u]);
    }

    return 0;
}