#include #include #include using namespace std; struct hrana { int x,y; bool obarvena; }; int N, M, D, K, A, B; vector stanice; vector hrany; vector< vector > G; // pro každý vrchol seznam čísel hran vedoucích z něho // Pomocná funkce: má-li hrana [h] jeden konec ve vrcholu [kde], kde je druhý konec? int druhy_konec(int h, int kde) { return hrany[h].x ^ hrany[h].y ^ kde; } // Počínaje ve vrcholech [odkud], obarví všechny hrany do vzdálenosti [maxdist] void obarvi(const vector &odkud, int maxdist) { vector vzdalenost( M+N, maxdist+1 ); queue Q; for (int x : odkud) { vzdalenost[x] = 0; Q.push(x); } while (!Q.empty()) { int kde = Q.front(); Q.pop(); if (vzdalenost[kde] == maxdist) continue; for (int h : G[kde]) { int kam = druhy_konec(h,kde); hrany[h].obarvena = true; if (vzdalenost[kam] == maxdist+1) { vzdalenost[kam] = vzdalenost[kde]+1; Q.push(kam); } } } } // Počínaje ve vrcholu [odkud], najdi všechny stanice dosažitelné // po obarvených hranách vector najdi_dosazitelne(int odkud) { vector navstivil( M+N, false ); queue Q; navstivil[odkud] = true; Q.push(odkud); while (!Q.empty()) { int kde = Q.front(); Q.pop(); for (int h : G[kde]) { if (!hrany[h].obarvena) continue; int kam = druhy_konec(h,kde); if (navstivil[kam]) continue; navstivil[kam] = true; Q.push(kam); } } vector odpoved; for (int s : stanice) if (navstivil[s]) odpoved.push_back(s); return odpoved; } int main() { // Načteme vstup cin >> N >> M >> D >> K >> A >> B; stanice.resize(D); for (int &s : stanice) cin >> s; stanice.push_back(A); // I kdyby v A nebyla stanice, na začátku tam jsme // a máme plnou baterii G.resize( N+M ); for (int m=0; m> x >> y; // místo původní hrany x-y přidáme dvě nové přes pomocný vrchol hrany.push_back( {x,N+m,false} ); // hrana číslo 2*m hrany.push_back( {y,N+m,false} ); // hrana číslo 2*m+1 G[x].push_back(2*m); G[N+m].push_back(2*m); G[y].push_back(2*m+1); G[N+m].push_back(2*m+1); } // Obarvi všechno do vzdálenosti K v novém grafu (tedy K/2 v původním) obarvi(stanice,K); // Najdi stanice, kam lze dojet po obarvených hranách vector dobre_stanice = najdi_dosazitelne(A); // Obarvi všechno do vzdálenosti 2*K od dobrých stanic for (auto &h : hrany) h.obarvena = false; obarvi(dobre_stanice,2*K); // Zjisti, zda můžeme dosáhnout B bool muzeme = false; for (int h : G[B]) if (hrany[h].obarvena) muzeme = true; cout << (muzeme ? "ano\n" : "ne\n"); }