Codeforces Round #804 (Div. 2)
5 өдрийн дараа |
B. Грэг ба граф
хугацааны хязгаарлалт 3 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Грэгд $n$ ширхэг оройноос тогтсон чиглэлтэй жинтэй граф байв. Графын орой бүр хоорондоо холбогдсон бөгөөд хоёр чиглэлтэй байна. Грэгд графаар тоглох таалагддаг тул ээлжит тоглоомоо зохиов:
Тоглоом $n$ үеэс тогтоно.
$i$-р үед ирэхэд Грэг $x_i$ дугаартай оройг графаас устгана. Оройг устгахад түүнээс гарж, орж байсан бүх ирмэгүүдийг бас устгана.
Үе бүрийн өмнө үйлдэл хийхээсээ өмнө Грэг бүх хос оройнуудыг холбосон хамгийн богино замуудын нийт уртыг мэдэхийг хүсжээ. Өөрөөр хэлбэл $v$-гээс $u$-рүү очих хамгийн богино замын урт нь $d(i, v, u)$ гэж үзвэл Грэг дараах нийлбэрийг мэдэхийг хүсэж байна: $\sum\limits_{v,u\ (v \neq u)} d(i, v, u)$.
Грэгд дээрх нийлбэрийг олохын тулд алхам бүр дээр нь туслаарай.
Оролт
Эхний мөрөнд графын оройн тоог илэрхийлэх бүхэл тоо $n$ $(1 ≤ n ≤ 500)$ өгөгдөнө.
Дараагийн $n$ мөрөнд матриц хэлбэрээр өгөгдсөн графын тодорхойлолт байх бөгөөд $i$-р мөрний $j$-р тоо нь $a_{ij}$ ($1 ≤ a_{ij} ≤ 10^5, a_{ii} = 0$) байна гэдэг нь $i$-р оройноос $j$-р орой руу чиглэсэн ирмэгийн жин юм.
Дараагийн мөрөнд Грэгийн устгасан оройнуудын дугаар болох давтагдаагүй $n$ ширхэг бүхэл тоо өгөгдөнө: $x_1, x_2, ..., x_n$ $(1 ≤ x_i ≤ n)$
Гаралт
$n$ бүхэл тоо хэвлэнэ үү. $i$-р үйлдэл хийхийн өмнөх замуудын уртын нийлбэр нь $i$-р тоотой тэнцэх ёстой.
Орчуулсан: Баттулга
Жишээ тэстүүд
Оролт
1 0 1
Гаралт
0
Оролт
2 0 5 4 0 1 2
Гаралт
9 0
Оролт
4 0 3 1 1 6 0 400 1 2 4 0 1 1 1 1 0 4 1 2 3
Гаралт
17 23 404 0