Zadanie
Krtko sa chce dostať z tej masívnej KSP párty domov, ale keďže sa prejedol torty, tak sa len tak kotúľa. Snaží sa kráčať, no každým krokom sa bojí, že sa preváži a spadne. Preto, koľko krokov spraví pravou nohou, toľko ich musí spraviť aj ľavou, aby to nejak vybalansoval. Ale keďže je hrooozne najedený, tak sa nechce úplne nachodiť.
Úloha
Daný je graf s \(n\) vrcholmi, očíslovanými od \(1\) po \(n\), ktorého vrcholy reprezentujú Krtkove pozície na ceste domov po krokoch – čo vrchol, to krok (kam Krtko spraví krok, tam sa posunie celým telom; nemôže byť nohami v dvoch vrcholoch naraz). V grafe sú samozrejme aj nejaké iné možnosti krokov, kam nie nutne musí stúpiť. Hrana z \(a\) do \(b\) znamená, že z vrcholu \(a\) vie do \(b\) prejsť na jeden krok.
Nájdite cestu párnej dĺžky z vrcholu číslo \(1\) (miesto, kde bola párty) do vrcholu číslo \(n\) (miesto, kde Krtko býva), kratšiu ako \(2n\) (nechce sa predsa nachodiť). Krtko sa samozrejme ale vie stratiť a zamotať, a teda môže prejsť v grafe cez vrchol aj viackrát a po hranách tiež.
Formát vstupu
V prvom riadku vstupu sú čísla \(n\) (\(1 \leq n \leq 10^5\)) počet vrcholov, a \(m\) (\(1 \leq m \leq 10^6\)) počet hrán.
Nasleduje \(m\) riadkov popisujúcich hrany. V každom z nich sú dve čísla oddelené medzerou, čísla vrcholov medzi ktorými je hrana.
Pre sady vstupov platia nasledovné obmedzenia:
Sada | 1 | 2 | 3 | 4 |
---|---|---|---|---|
\(n \leq\) | \(10\) | \(100\) | \(1\,000\) | \(10^5\) |
\(m \leq\) | \(10\) | \(1\,000\) | \(10^4\) | \(10^6\) |
Formát výstupu
Na jeden riadok vypíšte zaradom čísla vrcholov cez ktoré Krtkova cesta prechádza – do ktorých Krtko spraví krok, oddelené medzerou (vrátane vrcholu \(1\) a \(n\)). Ak žiadna vyhovujúca postupnosť neexistuje vypíšte \(-1\).
Príklady
Input:
6 6
1 6
3 2
2 4
5 4
4 3
3 6
Output:
1 6 3 2 4 3 6
Input:
6 6
1 2
2 3
3 4
2 5
3 6
5 6
Output:
-1
V tejto úlohe sme mali zadaný graf na \(n\) vrcholoch. Zaujímalo nás nájdenie takej cesty z vrchola 1 do vrchola \(n\), ktorá má párnu dĺžku menšiu ako \(2n\).
Pomalé riešenie
Zadanie úlohy vyzerá takmer ako bežné hľadanie najkratšej cesty. Jediným problémom je, že naša cesta musí mať párnu dĺžku.
Môžeme teda spraviť nasledovný trik. Vyrobíme si nový graf na vrcholoch 1 až \(n\). V tomto novom grafe bude hrana medzi každou dvojicou vrcholov \(a\), \(b\) takou, že v pôvodnom grafe boli \(a\), \(b\) vo vzdialenosti 2. Inak povedané, každá hrana v novom grafe bude predstavovať dve hrany pôvodného grafu.
Keď teraz nájdene najkratšiu cestu mezdi vrcholmi 1 a \(n\) v novom grafe, bude mať nejakú dĺžku \(d\). Táto cesta bude zodpovedať ceste dĺžky \(2d\) v pôvodnom grafe. Ak je \(2d < 2n\), našli sme vyhovujúce riešenie. Na hľadanie najkratšej cesty môžeme použiť vhodné prehľadávanie grafu.
Toto riešenie bude mať časovú zložitosť \(O(n^3)\) kvôli vytváraniu nového grafu.
import sys
200000)
sys.setrecursionlimit(
def dfs(a):
# print('a n:',a,n)
if visited[a] == True:
return []
if a == v-1:
return [a]
= True
visited[a] for b,c in G2[a]:
= dfs(b)
res if len(res) > 0:
res.append(c)
res.append(a)return res
return []
= map(int, input().split())
v, e = [[] for i in range(v)]
G for i in range(e):
= map(int, input().split())
a,b -= 1
a -= 1
b
G[a].append(b)
G[b].append(a)
= [[] for i in range(v)]
G2 for a in range(v):
for b in G[a]:
for c in G[a]:
if b < c:
G2[b].append((c,a))
G2[c].append((b,a))
= [False for i in range(v)]
visited = dfs(0)
res if len(res) == 0:
print(-1)
else:
print(*map(lambda x: x+1, reversed(res)))
#include <iostream>
#include <vector>
using namespace std;
int v,e;
<vector<pair<int, int>>> G2;
vector<bool> visited;
vector
<int> dfs(int a){
vector//# print('a n:',a,n)
<int> res;
vectorif (visited[a] == true)
return res;
if (a == v-1){
.push_back(a);
resreturn res;
}
[a] = true;
visitedfor (auto bc : G2[a]){
int b = bc.first;
int c = bc.second;
= dfs(b);
res if (res.size() > 0){
.push_back(c);
res.push_back(a);
resreturn res;
}
}
return res;
}
int main(){
>> v >> e;
cin <vector<int>> G(v);
vectorfor (int i=0; i<e; i++){
int a,b;
>> a >> b;
cin -= 1;
a -= 1;
b [a].push_back(b);
G[b].push_back(a);
G}
.resize(v);
G2for (int a=0; a<v; a++)
for (auto b : G[a])
for (auto c : G[a])
if (b < c){
[b].push_back({c,a});
G2[c].push_back({b,a});
G2}
.resize(v,false);
visited<int> res = dfs(0);
vectorif (res.size() == 0)
<<"-1"<<endl;
coutelse{
<<res[res.size()-1]+1;
coutfor (int i=res.size()-2; i>=0; i--)
<<' '<<res[i]+1;
cout<<endl;
cout}
}
Štandardná úloha
Táto úloha je celkom štandardná. Pri bežnom hľadaní najkratšej cesty si v každom vrchole pamätáme najmenšiu vzdialenosť, na ktorú sa do daného vrchola vieme dostať zo zdroja. My si ale v každom vrchole budeme pamätať dve informácie. Jedna z nich bude predstavovať najmenšiu párnu vzdialenosť, na ktorú sa do daného vrchola vieme dostať. Druhá bude analogicky predstavovať najmenšiu nepárnu vzdialenosť do daného vrchola zo zdroja.
Obe tieto informácie vieme počas prehľadávania grafu jednoducho aktualizovať. Princíp je rovnaký, ako pri obyčajnom BFS.
Netreba najkratšiu cestu
Zadanie od nás vyžaduje iba nájsť nejakú nie príliš dlhú párnu cestu. Namiesto BFS teda môžeme použiť aj DFS. Opäť budeme mať 2 kópie pôvodného grafu. Jednu nazveme nepárna, druhú párna. V každom kroku DFS sa presunieme do susedného vrchola, avšak v opačnej kópii. Prehľadávanie začneme v jednej z kópií vo vrchole 1. Ak sa nám podarí dostať do vrchola \(n\) v tej istej kópií, našli sme párnu cestu.
Ak niekedy počas prehľadávania prejdeme už viac, ako \(2n\) vrcholov, nevnoríme sa ďalej, pretože by takáto cesta bola príliš dlhá.
Takéto riešenie má časovú aj pamäťovú zložitosť \(O(n + m)\).
import sys
200000)
sys.setrecursionlimit(
def dfs(a, n):
# print('a n:',a,n)
if visited[n][a] == True:
return []
if n == 0 and a == v-1:
return [a]
= True
visited[n][a] for b in G[a]:
= dfs(b, n^1)
res if len(res) > 0:
res.append(a)return res
return []
= map(int, input().split())
v, e = [[] for i in range(v)]
G for i in range(e):
= map(int, input().split())
a,b -= 1
a -= 1
b
G[a].append(b)
G[b].append(a)
= [[False for i in range(v)], [False for i in range(v)]]
visited = dfs(0,0)
res if len(res) == 0:
print(-1)
else:
print(*map(lambda x: x+1, reversed(res)))
#include <iostream>
#include <vector>
using namespace std;
<vector<bool>> visited(2);
vectorint v, e;
<vector<int>> G;
vector
<int> dfs(int a, int n){
vector//# print('a n:',a,n)
<int> res;
vectorif (visited[n][a] == true)
return res;
if (n == 0 and a == v-1){
.push_back(a);
resreturn res;
}
[n][a] = true;
visitedfor(auto b : G[a]){
= dfs(b, n^1);
res if (res.size() > 0){
.push_back(a);
resreturn res;
}
}
return res;
}
int main(){
>> v >> e;
cin .resize(v);
G
for (int i=0; i<e; i++){
int a, b;
>> a >> b;
cin -= 1;
a -= 1;
b [a].push_back(b);
G[b].push_back(a);
G}
[0].resize(v,false);
visited[1].resize(v,false);
visited<int> res = dfs(0,0);
vectorif (res.size() == 0)
<<"-1"<<endl;
coutelse {
<<res[res.size()-1]+1;
coutfor (int i=res.size()-2; i>=0; i--)
<<' '<<res[i]+1;
cout<<endl;
cout}
}
Diskusia
Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.
Pre pridávanie komentárov sa musíš prihlásiť.