prisonbreak

Algoritmul, pas cu pas

Un drum $1 \to N$ valid folosește cel mult $2$ culori la nodurile intermediare (nodurile $1$ și $N$ sunt necolorate, deci mereu permise). Cheia: ducem informația despre culorile folosite în starea căutării.

Dijkstra pe stări

Starea e perechea $(\text{nod},\ S)$, unde $S$ e mulțimea exactă a culorilor folosite pe drum până acum, de cel mult $2$ culori. Tranziție de la $(v, S)$ pe un vecin $w$:

• formăm $S' = S \cup \{\text{culoare}(w)\}$ (dacă $w$ e colorat);
• dacă $|S'| > 2$, mutarea e interzisă (am folosi $3$ culori);
• altfel relaxăm starea $(w, S')$ cu costul $\text{dist}(v, S) + c(v, w)$.

Rulăm Dijkstra peste aceste stări. Costul minim e $\min_S \text{dist}(N, S)$.

Numărarea și reconstituirea

Pe lângă distanță ținem, pentru fiecare stare:

• $\text{cnt}$ — numărul de drumuri de cost minim până la ea (modulo $666\,013$); când relaxăm strict, copiem $\text{cnt}$; când găsim un cost egal, adunăm $\text{cnt}$-urile;
• $\text{parinte}$ — starea din care am ajuns la cost minim, pentru a reconstrui un drum la final.

Numărul cerut e suma $\text{cnt}$-urilor stărilor $(N, S)$ care ating costul minim. Fiindcă fiecare drum are o mulțime exactă de culori, nu numărăm de două ori același drum.