Arcadia Computing Contest 2 P5 - lp0 is on fire!

    1#include <bits/stdc++.h>
    2using namespace std;
    3using ll = long long;
    4using i128 = __int128;
    5const int inf = 1e9;
    6const ll INF = 2e18; //❄️
    7int main() {
    8    ios::sync_with_stdio(0); cin.tie(0);
    9    int n, m, k; ll t; cin >> n >> m >> k >> t;
    10    vector<char> v(n + 1);
    11    for (int i = 0; i < k; i++) {
    12        int x; cin >> x;
    13        v[x] = 1;
    14    }
    15    vector<vector<pair<int, int>>> adj(n + 1);
    16    for (int i = 0; i < m; i++) {
    17        int u, v, w; cin >> u >> v >> w;
    18        adj[u].emplace_back(w, v);
    19        adj[v].emplace_back(w, u);
    20    }
    21    vector<ll> dist(n + 1, INF);
    22    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
    23    //muti source dijkstras
    24    for (int i = 1; i <= n; i++) {
    25        if (!v[i]) {
    26            pq.push({0, i});
    27            dist[i] = 0;
    28        }
    29    }
    30    while (!pq.empty()) {
    31        auto[w, u] = pq.top(); pq.pop();
    32        if (w > dist[u]) continue;
    33        for (auto[c, v] : adj[u]) {
    34            if (w + c < dist[v]) {
    35                dist[v] = w + c;
    36                pq.push({dist[v], v});
    37            }
    38        }
    39    }
    40    for (int i = 1; i <= n; i++) {
    41        cout << (dist[i] <= t ? 0 : 1) << (i == n ? "\n" : "");
    42    }
    43    return 0;
    44}