3107 | 2023. 02. 15 18:15:36 | horvathabel | Tom és Jerry 1 (80) | cpp17 | Elfogadva 80/80 | 114ms | 17048 KiB |
#include <bits/stdc++.h>
using namespace std;
int maxn=100001;
vector<pair<int,int>> g[100001];
vector<int> tomt(maxn);
void bfst(int t){
bool seen[maxn];
tomt[t]=0;
queue<int> q;
q.push(t);
seen[t]=true;
while (!q.empty()){
int v=q.front();
q.pop();
for (auto edge:g[v]){
if (edge.second==2 && !seen[edge.first]){
tomt[edge.first]=tomt[v]+1;
seen[edge.first]=true;
q.push(edge.first);
}
}
}
tomt[t]=-1;
}
vector<int> tavok(maxn);
void bfse(int e){
vector<bool> seen;
seen.assign(maxn, 0);
tavok[e]=maxn;
priority_queue<pair<int,int>> q;
q.push({tavok[e],e});
seen[e]=true;
while (!q.empty()){
int v=q.top().second;
q.pop();
for (auto edge:g[v]){
if (!seen[edge.first]){
if (tomt[edge.first]==0) tavok[edge.first]=tavok[v]-1;
else{
tavok[edge.first]=min(tomt[edge.first]-1, tavok[v]-1);
}
q.push({tavok[edge.first],edge.first});
seen[edge.first]=true;
}
}
}
}
int main() {
int n,m,t,j,e;
cin>>n>>m>>t>>j>>e;
for (int i=0; i<m;i++){
int x,y,z;
cin>>x>>y>>z;
g[x].push_back(make_pair(y,z));
g[y].push_back(make_pair(x,z));
}
bfst(t);
bfse(e);
for (int i=0; i<j;i++){
int x;
cin >>x;
if (tavok[x]>=0 && x!=t) cout<<"IGEN"<<endl;
else cout<<"NEM"<<endl;
}
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 80/80 | ||||||
1 | Elfogadva | 0/0 | 6ms | 7900 KiB | |||
2 | Elfogadva | 0/0 | 7ms | 8560 KiB | |||
3 | Elfogadva | 4/4 | 4ms | 8448 KiB | |||
4 | Elfogadva | 4/4 | 6ms | 8660 KiB | |||
5 | Elfogadva | 4/4 | 4ms | 8616 KiB | |||
6 | Elfogadva | 4/4 | 4ms | 8948 KiB | |||
7 | Elfogadva | 4/4 | 6ms | 9164 KiB | |||
8 | Elfogadva | 4/4 | 6ms | 9160 KiB | |||
9 | Elfogadva | 4/4 | 7ms | 9408 KiB | |||
10 | Elfogadva | 4/4 | 8ms | 9548 KiB | |||
11 | Elfogadva | 4/4 | 14ms | 10276 KiB | |||
12 | Elfogadva | 4/4 | 17ms | 10776 KiB | |||
13 | Elfogadva | 4/4 | 26ms | 11512 KiB | |||
14 | Elfogadva | 4/4 | 48ms | 13168 KiB | |||
15 | Elfogadva | 4/4 | 67ms | 14144 KiB | |||
16 | Elfogadva | 4/4 | 72ms | 14468 KiB | |||
17 | Elfogadva | 4/4 | 101ms | 16212 KiB | |||
18 | Elfogadva | 4/4 | 68ms | 14368 KiB | |||
19 | Elfogadva | 4/4 | 93ms | 14184 KiB | |||
20 | Elfogadva | 4/4 | 78ms | 14168 KiB | |||
21 | Elfogadva | 4/4 | 71ms | 13964 KiB | |||
22 | Elfogadva | 4/4 | 114ms | 17048 KiB |