123702024-12-13 15:28:57Ablablabla1Tom és Jerry 1 (80)cpp17Wrong answer 76/80123ms5836 KiB
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int INF = 2e9 + 7;

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

int main()
{
    int n, m, t, q, j;
    cin >> n >> m >> t >> q >> j;
    t--; j--;

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

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

    vector<int> tavok(n, INF);
    vector<bool> bejart(n);
    queue<int> bejar;
    bejar.push(t);
    tavok[t] = 0;

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

        if(bejart[akt]) continue;

        bejart[akt] = 1;

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

            tavok[x.first] = tavok[akt] + 1;
            bejar.push(x.first);
        }
    }

    bejart.assign(n, 0);
    priority_queue<pii, vector<pii>, comp> hely;
    hely.push({j, tavok[j]});

    while(!hely.empty()){
        int akt = hely.top().first;
        int marad = hely.top().second;
        hely.pop();

        if(bejart[akt]) continue;

        bejart[akt] = 1;

        if(marad == 1) continue;

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

            hely.push({x.first, min(marad - 1 + (marad == INF), tavok[x.first])});
        }
    }

    while(q--){
        int a;
        cin >> a;
        a--;

        if(bejart[a]){
            cout << "IGEN\n";
        } else{
            cout << "NEM\n";
        }
    }
}
SubtaskSumTestVerdictTimeMemory
base76/80
1Accepted0/01ms320 KiB
2Accepted0/03ms320 KiB
3Accepted4/41ms508 KiB
4Accepted4/41ms320 KiB
5Accepted4/41ms320 KiB
6Accepted4/41ms320 KiB
7Accepted4/41ms320 KiB
8Accepted4/42ms320 KiB
9Accepted4/43ms320 KiB
10Accepted4/43ms336 KiB
11Accepted4/410ms780 KiB
12Accepted4/412ms1080 KiB
13Accepted4/424ms1672 KiB
14Accepted4/446ms2968 KiB
15Wrong answer0/468ms3776 KiB
16Accepted4/467ms4408 KiB
17Accepted4/4101ms5012 KiB
18Accepted4/467ms3896 KiB
19Accepted4/481ms4152 KiB
20Accepted4/479ms4152 KiB
21Accepted4/468ms3548 KiB
22Accepted4/4123ms5836 KiB