5755 | 2023. 09. 16 18:50:04 | Ablablabla | Tom és Jerry 1 (80) | cpp17 | Elfogadva 80/80 | 122ms | 20012 KiB |
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int NINF = -2e9 - 7;
const int INF = 2e9 + 7;
struct comp{
bool operator()(pii a, pii b){
return a.second < b.second;
}
};
int main()
{
int n, m, t, p, e;
cin >> n >> m >> t >> p >> e;
t--;
e--;
vector<vector<pii>> csucsok(n, vector<pii>(0, {0, 0}));
for(int i = 0; i < m; i++){
int a, b, c;
cin >> a >> b >> c;
a--; b--;
csucsok[a].push_back({b, c});
csucsok[b].push_back({a, c});
}
vector<int> tTavok(n, INF);
queue<int> bejar;
bejar.push(t);
vector<bool> bejart(n, 0);
bejart[t] = 1;
int aktualis = 1;
int kovi = 0;
int melyseg = 0;
while(!bejar.empty()){
int akt = bejar.front();
bejar.pop();
tTavok[akt] = melyseg;
for(pii x : csucsok[akt]){
if(bejart[x.first]) continue;
if(x.second != 2) continue;
bejart[x.first] = 1;
bejar.push(x.first);
kovi++;
}
aktualis--;
if(aktualis == 0){
melyseg++;
swap(kovi, aktualis);
}
}
priority_queue<pii, vector<pii>, comp> sor;
sor.push({e, INF});
vector<int> elerheto(n, NINF);
elerheto[e] = INF;
bejart.assign(n, 0);
bejart[e] = 1;
while(!sor.empty()){
pii akt = sor.top();
sor.pop();
for(pii x : csucsok[akt.first]){
if(bejart[x.first]) continue;
bejart[x.first] = 1;
elerheto[x.first] = min(tTavok[x.first] - 1, akt.second - 1);
sor.push({x.first, elerheto[x.first]});
}
}
for(int i = 0; i < p; i++){
int a;
cin >> a;
a--;
if(elerheto[a] >= 0){
cout << "IGEN\n";
} else{
cout << "NEM\n";
}
}
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 80/80 | ||||||
1 | Elfogadva | 0/0 | 3ms | 1816 KiB | |||
2 | Elfogadva | 0/0 | 4ms | 2248 KiB | |||
3 | Elfogadva | 4/4 | 3ms | 2240 KiB | |||
4 | Elfogadva | 4/4 | 3ms | 2384 KiB | |||
5 | Elfogadva | 4/4 | 3ms | 2468 KiB | |||
6 | Elfogadva | 4/4 | 3ms | 2448 KiB | |||
7 | Elfogadva | 4/4 | 3ms | 2476 KiB | |||
8 | Elfogadva | 4/4 | 4ms | 2808 KiB | |||
9 | Elfogadva | 4/4 | 4ms | 3260 KiB | |||
10 | Elfogadva | 4/4 | 4ms | 3636 KiB | |||
11 | Elfogadva | 4/4 | 10ms | 4288 KiB | |||
12 | Elfogadva | 4/4 | 14ms | 5248 KiB | |||
13 | Elfogadva | 4/4 | 21ms | 6184 KiB | |||
14 | Elfogadva | 4/4 | 45ms | 8780 KiB | |||
15 | Elfogadva | 4/4 | 64ms | 10596 KiB | |||
16 | Elfogadva | 4/4 | 67ms | 13988 KiB | |||
17 | Elfogadva | 4/4 | 97ms | 15608 KiB | |||
18 | Elfogadva | 4/4 | 64ms | 14248 KiB | |||
19 | Elfogadva | 4/4 | 85ms | 15284 KiB | |||
20 | Elfogadva | 4/4 | 71ms | 16012 KiB | |||
21 | Elfogadva | 4/4 | 67ms | 15704 KiB | |||
22 | Elfogadva | 4/4 | 122ms | 20012 KiB |