78152024-01-11 11:01:58BenedekMartonTom és Jerry 1 (80)cpp17Időlimit túllépés 64/80569ms13964 KiB
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main()
{
    //beolvasas
    int n, m, t, p, e;
    cin >> n >> m >> t >> p >> e;
    t--;
    e--;
    vector<int> jar1[n], jar2[n];
    int a, b, s, k[p];
    for(int i=0; i<m; i++)
    {
        cin >> a >> b >> s;
        a--; b--;
        if(s==1)
        {
            jar1[a].push_back(b);
            jar1[b].push_back(a);
        }
        else
        {
            jar1[a].push_back(b);
            jar1[b].push_back(a);
            jar2[a].push_back(b);
            jar2[b].push_back(a);
        }
    }
    //cout << "Ce e problema";
    for(int i=0; i<p; i++)
    {
        cin >> k[i];
        k[i]--;
    }

    //tom
    int tid[n], x;
    for(int i=0; i<n; i++)
    {
        tid[i]=-1;
    }
    queue<int> q;
    tid[t]=0;
    q.push(t);
    while(!q.empty())
    {
        x=q.front();
        q.pop();
        for(int i=0; i<jar2[x].size(); i++)
        {
            if(tid[jar2[x][i]]==-1)
            {
                tid[jar2[x][i]]=tid[x]+1;
                q.push(jar2[x][i]);
            }
        }
    }

    //egerke
    int jid[n];
    for(int i=0; i<p; i++)
    {
        for(int j=0; j<n; j++)
        {
            jid[j]=-1;
        }
        jid[k[i]]=0;
        q.push(k[i]);
        while(!q.empty())
        {
            x=q.front();
            q.pop();
            for(int j=0; j<jar1[x].size(); j++)
            {
                if(jid[jar1[x][j]]==-1 and (!(tid[jar1[x][j]]<=jid[x]+1) or tid[jar1[x][j]]==-1))
                {
                    jid[jar1[x][j]]=jid[x]+1;
                    q.push(jar1[x][j]);
                }
            }
        }
        if(jid[e]!=-1)
        {
            cout << "IGEN" << endl;
        }
        else
        {
            cout << "NEM" << endl;
        }
    }
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base64/80
1Elfogadva0/03ms1824 KiB
2Elfogadva0/04ms2136 KiB
3Elfogadva4/43ms2076 KiB
4Elfogadva4/43ms2288 KiB
5Elfogadva4/43ms2380 KiB
6Elfogadva4/43ms2504 KiB
7Elfogadva4/43ms2888 KiB
8Elfogadva4/44ms2908 KiB
9Elfogadva4/44ms3044 KiB
10Elfogadva4/44ms3392 KiB
11Elfogadva4/412ms3824 KiB
12Elfogadva4/416ms5264 KiB
13Elfogadva4/426ms5748 KiB
14Elfogadva4/448ms8380 KiB
15Elfogadva4/471ms8640 KiB
16Elfogadva4/475ms13964 KiB
17Elfogadva4/4115ms12920 KiB
18Elfogadva4/470ms10468 KiB
19Időlimit túllépés0/4555ms7112 KiB
20Időlimit túllépés0/4565ms7196 KiB
21Időlimit túllépés0/4558ms6024 KiB
22Időlimit túllépés0/4569ms7364 KiB