2386 | 2023. 01. 12 10:45:36 | renn | Tom és Jerry 1 (80) | cpp11 | Időlimit túllépés 64/80 | 575ms | 17592 KiB |
#include <bits/stdc++.h>
using namespace std;
//http://tamop412.elte.hu/tananyagok/algoritmusok/lecke24_lap1.html
void tbejar(vector<int> graf[], int eleres[], int size, int pos)
{
queue<int> pospool;
bool volt[size];
pospool.push(pos);
volt[pos] = true;
int k;
while(!pospool.empty())
{
k = pospool.front();
pospool.pop();
for(int i : graf[k])
{
if(eleres[i] > eleres[k]+1)
{
eleres[i] = eleres[k]+1;
pospool.push(i);
}
}
}
}
bool jbejar(vector<int> graf[], int jeleres[], int teleres[],
int size, int pos, int cel)
{
if(cel == pos)
return true;
if(teleres[pos] == 0)
return false;
queue<int> pospool;
fill(jeleres, jeleres+size, INT_MAX);
jeleres[pos] = 0;
pospool.push(pos);
int k;
while(!pospool.empty())
{
k = pospool.front();
pospool.pop();
for(int i : graf[k])
{
if(jeleres[i] > jeleres[k]+1)
{
if(jeleres[k]+1 < teleres[i])
{
if(i == cel)
return true;
jeleres[i] = jeleres[k]+1;
pospool.push(i);
}
}
}
}
return false;
}
int main()
{
iostream::sync_with_stdio(0);
cin.tie(0);
int pontok, jaratok, tom, probaszam, haz;
cin >> pontok >> jaratok >> tom >> probaszam >> haz;
tom--;
haz--;
vector<int> tgraf[pontok];
vector<int> jgraf[pontok];
int teleres[pontok];
int jeleres[pontok];
fill(teleres, teleres+pontok, INT_MAX);
teleres[tom] = 0;
int a, b, c;
for(int i = 0; i < jaratok; i++)
{
cin >> a >> b >> c;
if(c == 2)
{
tgraf[a-1].push_back(b-1);
tgraf[b-1].push_back(a-1);
}
jgraf[a-1].push_back(b-1);
jgraf[b-1].push_back(a-1);
}
tbejar(tgraf, teleres, pontok, tom);
int proba;
for(int i = 0; i < probaszam; i++)
{
cin >> proba;
proba--;
if(jbejar(jgraf, jeleres, teleres, pontok, proba, haz))
{
cout << "IGEN\n";
}
else cout << "NEM\n";
}
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 64/80 | ||||||
1 | Elfogadva | 0/0 | 3ms | 1828 KiB | |||
2 | Elfogadva | 0/0 | 3ms | 2260 KiB | |||
3 | Elfogadva | 4/4 | 2ms | 2120 KiB | |||
4 | Elfogadva | 4/4 | 2ms | 2328 KiB | |||
5 | Elfogadva | 4/4 | 2ms | 2572 KiB | |||
6 | Elfogadva | 4/4 | 2ms | 2748 KiB | |||
7 | Elfogadva | 4/4 | 3ms | 2852 KiB | |||
8 | Elfogadva | 4/4 | 3ms | 3208 KiB | |||
9 | Elfogadva | 4/4 | 3ms | 3440 KiB | |||
10 | Elfogadva | 4/4 | 3ms | 3760 KiB | |||
11 | Elfogadva | 4/4 | 7ms | 4284 KiB | |||
12 | Elfogadva | 4/4 | 8ms | 5772 KiB | |||
13 | Elfogadva | 4/4 | 13ms | 6632 KiB | |||
14 | Elfogadva | 4/4 | 26ms | 10048 KiB | |||
15 | Elfogadva | 4/4 | 32ms | 11236 KiB | |||
16 | Elfogadva | 4/4 | 41ms | 17420 KiB | |||
17 | Elfogadva | 4/4 | 61ms | 17592 KiB | |||
18 | Elfogadva | 4/4 | 34ms | 15844 KiB | |||
19 | Időlimit túllépés | 0/4 | 575ms | 13312 KiB | |||
20 | Időlimit túllépés | 0/4 | 561ms | 13808 KiB | |||
21 | Időlimit túllépés | 0/4 | 561ms | 13376 KiB | |||
22 | Időlimit túllépés | 0/4 | 563ms | 15904 KiB |