E. Буруу Флойд

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Валера хамгийн богино зам оллох алгоритмууд туршиж үзнэ. Тэр саяхан Флойдын алгоритм сурсан ба одоо үүнтэй ажиллах цаг иржээ.

Валера $n$ орой, $m$ ирмэгээс тогтох чиглэлгүй холбоост граф (гогцоогүй ба аль ч хоёр оройг ихдээ нэг л ирмэг холбоно) дахь дурын 2 оройн хоорондын хамгийн богино зайг тооцоохлох код биччихсэн. Үүний хажуугаар Валера зарим оройг тэмдэглэхээр шийдэж $a_1,a_2,...,a_k$ оройнуудыг тэмдэглэжээ.

Доорх нь Валерагийн код:

ans[i][j] // the shortest distance for a pair of vertexes i, j a[i] // vertexes, marked by Valera

for(i = 1; i <= n; i++) { $\space$$\space$$\space$$\space$$\space$ for(j = 1; j <= n; j++) { $\space$$\space$$\space$$\space$$\space$$\space$$\space$$\space$$\space$$\space$$\space$ if (i == j) $\space$$\space$$\space$$\space$$\space$$\space$$\space$$\space$$\space$$\space$$\space$$\space$$\space$$\space$$\space$ ans[i][j] = 0; $\space$$\space$$\space$$\space$$\space$$\space$$\space$$\space$$\space$$\space$$\space$ else $\space$$\space$$\space$$\space$$\space$$\space$$\space$$\space$$\space$$\space$$\space$$\space$$\space$$\space$$\space$ ans[i][j] = INF; //INF is a very large number $\space$$\space$$\space$$\space$$\space$ } }

for(i = 1; i <= m; i++) { read a pair of vertexes u, v that have a non-directed edge between them; ans[u][v] = 1; ans[v][u] = 1; }

for (i = 1; i <= k; i++) { $\space$$\space$$\space$$\space$$\space$$\space$v = a[i]; $\space$$\space$$\space$$\space$$\space$$\space$ for(j = 1; j <= n; j++) $\space$$\space$$\space$$\space$$\space$$\space$$\space$$\space$$\space$$\space$$\space$$\space$ for(r = 1; r <= n; r++) $\space$$\space$$\space$$\space$$\space$$\space$$\space$$\space$$\space$$\space$$\space$$\space$$\space$$\space$$\space$$\space$$\space$$\space$ ans[j][r] = min(ans[j][r], ans[j][v] + ans[v][r]); } Валера код нь алдаатай байгааг ажиглажээ. Тэмдэглэгдсэн оройнуудын олонлог $a_1,a_2,...,a_k$ өгөгдсөн бол Валерагийн код буруу ажиллах $n$ орой, $m$ ирмэгээс тогтох чиглэлгүй холбоост граф олно уу.(ядаж нэг хос оройн хоорондын хамгийн богино зайг буруу олж байх ёстой.) Мөн энэ граф нь давхар ирмэггүй, гогцоогүй байх ёстой. Ийм граф олдохгүй бол -1 гэж хэвлэ.

Оролт

Эхний мөрөнд харгалзан орой, ирмэгийн тоо болон тэмдэглэгдсэн оройн тоо $n,m,k (3\le n\le 300, 2\le k\le n , m-1\le m\le \frac{n(n-1)}{2})$ өгөгдөнө.

Удаах мөрөнд зайгаар тусгаардлагдсан $a_1,a_2,... ,a_k (1\le a_i\le n)$ $k$ ширхэг тоонууд өгөгдөнө.

Гаралт

Нөхцөлийг хангах граф олдохгүй бол "-1" гэж хэвлэ. Олдох бол $m$ мөрөнд мөр тус бүр нь Валерагийн хайж буй графийн ирмэгүүдийг тодорхойлох $u,v$ бүхэл тоонууд өгөгдөнө.

Орчуулсан: Төрбат

Жишээ тэстүүд

Оролт
3 2 2
1 2
Гаралт
1 3
2 3
Оролт
3 3 2
1 2
Гаралт
-1
Сэтгэгдлүүдийг ачааллаж байна...