57552023-09-16 18:50:04AblablablaTom és Jerry 1 (80)cpp17Elfogadva 80/80122ms20012 KiB
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int NINF = -2e9 - 7;
const int INF = 2e9 + 7;

struct comp{
    bool operator()(pii a, pii b){
        return a.second < b.second;
    }
};

int main()
{
    int n, m, t, p, e;
    cin >> n >> m >> t >> p >> e;
    t--;
    e--;

    vector<vector<pii>> csucsok(n, vector<pii>(0, {0, 0}));
    for(int i = 0; i < m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;

        csucsok[a].push_back({b, c});
        csucsok[b].push_back({a, c});
    }

    vector<int> tTavok(n, INF);
    queue<int> bejar;
    bejar.push(t);
    vector<bool> bejart(n, 0);
    bejart[t] = 1;
    int aktualis = 1;
    int kovi = 0;
    int melyseg = 0;

    while(!bejar.empty()){
        int akt = bejar.front();
        bejar.pop();

        tTavok[akt] = melyseg;

        for(pii x : csucsok[akt]){
            if(bejart[x.first]) continue;
            if(x.second != 2) continue;

            bejart[x.first] = 1;
            bejar.push(x.first);
            kovi++;
        }

        aktualis--;
        if(aktualis == 0){
            melyseg++;
            swap(kovi, aktualis);
        }
    }

    priority_queue<pii, vector<pii>, comp> sor;
    sor.push({e, INF});
    vector<int> elerheto(n, NINF);
    elerheto[e] = INF;
    bejart.assign(n, 0);
    bejart[e] = 1;

    while(!sor.empty()){
        pii akt = sor.top();
        sor.pop();

        for(pii x : csucsok[akt.first]){
            if(bejart[x.first]) continue;

            bejart[x.first] = 1;
            elerheto[x.first] = min(tTavok[x.first] - 1, akt.second - 1);
            sor.push({x.first, elerheto[x.first]});
        }
    }

    for(int i = 0; i < p; i++){
        int a;
        cin >> a;
        a--;

        if(elerheto[a] >= 0){
            cout << "IGEN\n";
        } else{
            cout << "NEM\n";
        }
    }
}