1779 | 2022. 12. 03 12:24:39 | bzsofia | Tom és Jerry 1 (80) | cpp11 | Időlimit túllépés 64/80 | 569ms | 16516 KiB |
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct adat
{
int tav=-1;
vector <int> sz;
bool lat;
};
queue <int> s;
int i, n, m, tkezd, jkezd, cel, t, a, b, c, akt, j;
int main()
{
cin>>n>>m>>tkezd>>t>>cel;
vector <adat> jerry(n+1), tom(n+1);
for (i=1; i<=m; ++i)
{
cin>>a>>b>>c;
if (c==2)
{
tom[a].sz.push_back(b);
tom[b].sz.push_back(a);
}
jerry[a].sz.push_back(b);
jerry[b].sz.push_back(a);
}
tom[tkezd].tav=0;
tom[tkezd].lat=1;
s.push(tkezd);
while (!s.empty())
{
akt=s.front();
s.pop();
for (auto &e:tom[akt].sz)
{
if (!tom[e].lat)
{
tom[e].lat=1;
tom[e].tav=tom[akt].tav+1;
s.push(e);
}
}
}
for (i=1; i<=t; ++i)
{
cin>>jkezd;
for (j=1; j<=n; ++j)
{
jerry[j].tav=-1;
jerry[j].lat=0;
}
jerry[jkezd].tav=0;
jerry[jkezd].lat=1;
s.push(jkezd);
while (!s.empty())
{
akt=s.front();
s.pop();
for (auto &e:jerry[akt].sz)
{
if (!jerry[e].lat && (jerry[akt].tav+1<tom[e].tav || tom[e].tav==-1))
{
jerry[e].lat=1;
jerry[e].tav=jerry[akt].tav+1;
s.push(e);
}
}
}
if (jerry[cel].tav>-1) cout<<"IGEN\n";
else cout<<"NEM\n";
}
return 0;
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 64/80 | ||||||
1 | Elfogadva | 0/0 | 3ms | 1720 KiB | |||
2 | Elfogadva | 0/0 | 4ms | 2248 KiB | |||
3 | Elfogadva | 4/4 | 2ms | 2168 KiB | |||
4 | Elfogadva | 4/4 | 2ms | 2412 KiB | |||
5 | Elfogadva | 4/4 | 2ms | 2588 KiB | |||
6 | Elfogadva | 4/4 | 2ms | 2672 KiB | |||
7 | Elfogadva | 4/4 | 3ms | 2864 KiB | |||
8 | Elfogadva | 4/4 | 4ms | 3152 KiB | |||
9 | Elfogadva | 4/4 | 4ms | 3268 KiB | |||
10 | Elfogadva | 4/4 | 4ms | 3504 KiB | |||
11 | Elfogadva | 4/4 | 10ms | 3808 KiB | |||
12 | Elfogadva | 4/4 | 16ms | 5248 KiB | |||
13 | Elfogadva | 4/4 | 27ms | 5896 KiB | |||
14 | Elfogadva | 4/4 | 50ms | 9264 KiB | |||
15 | Elfogadva | 4/4 | 75ms | 9588 KiB | |||
16 | Elfogadva | 4/4 | 79ms | 16516 KiB | |||
17 | Elfogadva | 4/4 | 118ms | 14588 KiB | |||
18 | Elfogadva | 4/4 | 82ms | 11792 KiB | |||
19 | Időlimit túllépés | 0/4 | 551ms | 8536 KiB | |||
20 | Időlimit túllépés | 0/4 | 558ms | 8716 KiB | |||
21 | Időlimit túllépés | 0/4 | 569ms | 7148 KiB | |||
22 | Időlimit túllépés | 0/4 | 546ms | 8620 KiB |