SP-T001: Tunnel System

#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];
bool visited[N + 1];
lli dist[N + 1], wifiDist[N + 1];

int main(){

    int nVertex, nEdge, nWifi, st, ed;
    lli radius;
    scanf("%d%d%d%lld%d%d", &nVertex, &nEdge, &nWifi, &radius, &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);
    }

    for(int i = 1; i <= nVertex; ++i){
        dist[i] = 1e18;
        wifiDist[i] = -1;
    }
    priority_queue<pli, vector<pli>, greater<pli>> pq;
    for(int i = 1; i <= nWifi; ++i){
        int u;
        scanf("%d", &u);
        dist[u] = 0;
        pq.emplace(0, u);
    }
    while(!pq.empty()){
        int u = pq.top().second;
        pq.pop();
        if(wifiDist[u] != -1){
            continue;
        }
        wifiDist[u] = radius - dist[u];
        for(pii nxt : adj[u]){
            int v = nxt.first;
            int w = nxt.second;
            if(wifiDist[v] == -1 && dist[u] + w < dist[v] && dist[u] + w <= radius){
                dist[v] = dist[u] + w;
                pq.emplace(dist[v], v);
            }
        }
    }

    // Dijkstra Setup
    for(int i = 1; i <= nVertex; ++i){
        dist[i] = 1e18;
        visited[i] = false;
    }
    if(wifiDist[st] == -1){
        cout << "Impossible";
        return 0;
    }
    // Dijkstra Algorithm
    dist[st] = 0;
    pq.emplace(dist[st], st);
    while(!pq.empty()){
        int u = pq.top().second;
        pq.pop();
        if(visited[u]){
            continue;
        }
        if(u == ed){
            cout << dist[ed];
            return 0;
        }
        visited[u] = true;
        for(pii nxt : adj[u]){
            int v = nxt.first;
            int w = nxt.second;
            if(!visited[v] && dist[u] + w < dist[v] && wifiDist[v] >= 0 && wifiDist[u] + wifiDist[v] >= w){
                dist[v] = dist[u] + w;
                pq.emplace(dist[v], v);
            }
        }
    }
    cout << "Impossible";

    return 0;
}