Böyük Manilada dolanma

Manila Metropoliteni hazırda konsentrik yarımdairələr kimi yerləşdirilmiş beş halqa yoldan ibarətdir və tezliklə şimal və cənubu birləşdirəcək altıncı yol tikiləcək. Mərkəzdən (Manila) çıxan on radial yol Metro Manilanın daxili və xarici ərazilərini birləşdirir.

Şəkil 1 Manila üçün ideal yol şəbəkəsi

Bu məsələdə məqsəd A nöqtəsindən B nöqtəsinə ən qısa məsafəni tapmaqdır. Hər nöqtə halqa və radial yolun kəsişməsi (C#,R#) kimi verilir, mərkəz isə (C0,R0) kimi təyin edilir.

Hesablamalarda radial yol boyunca hər bir seqmentin uzunluğu $1$ vahid, halqa yolunun bir qövsünün uzunluğu isə həmin halqa yolunun nömrəsinə bərabərdir. Məsələn, (\textbf{C1}, \textbf{R3})-dən (\textbf{C2}, \textbf{R3})-ə qədər məsafə $1$ vahiddir, (\textbf{C3}, \textbf{R1})-dən (\textbf{C3}, \textbf{R2})-ə qədər isə $3$ vahiddir. (\textbf{C1}, \textbf{R2})-dən (\textbf{C5}, \textbf{R1})-ə ən qısa məsafə $5$ vahiddir (qalınlaşdırılmış yol şəklində göstərilib). Bu məsələdə $\text{C6}$ boyunca hərəkət mümkündür.

Lakin yeni nömrə kodlaşdırma sistemi tətbiq edildiyi üçün nəqliyyat vasitələri nömrənin son rəqəmi ilə eyni olan radial yoldan istifadə edə bilməzlər. Məsələn, dövlət nömrə nişanı ABC-123 olan avtomobil $\text{R3}$ yolundan istifadə edə bilməz. Halqa yollarında (yalnız $\text{C6}$ istisna olmaqla) da məhdudiyyətlər var: nömrənin sonu $1,2$ olarsa $\text{C1}$, $3,4$ olarsa $\text{C2}$, $5,6$ olarsa $\text{C3}$, $7,8$ olarsa $\text{C4}$, $9,0$ olarsa $\text{C5}$ istifadəsi qadağandır. Buna görə (\textbf{C1}, \textbf{R2})-dən (\textbf{C5}, \textbf{R1})-ə qədər ən qısa məsafə ABC-123 üçün $5$, CBA-321 üçün isə $9$ vahiddir. Qeyd edək ki, bəzən heç bir yol tapılmaya bilər.