Форум Всеукраїнської інтернет-олімпіади NetOI

Какие ограничения по времени?

seland написав:

У тестовому прикладі час проходження інформації з 1 в 2 дорівнює 1, а в іншу сторону з 2 в 1 записано, що зв'язку немає(тобто 0), хоча також сказано, що час однаковий в обидва боки. Це помилка у тестовому прикладі?

Дякуємо за зауваження, виправили.

У i-му рядку на j-й позиції записано час проходження інформації від i-го до j-го сервера – натуральне число від 1 до 100000. Якщо між i-м та j-м серверами немає виділеної лінії, записується 0.

Понятно, что на главной диагонали будут стоять нули. Кто в трезвом уме проведёт выделенную линию между сервером и... Этим же сервером.

Наступні N рядків містять опис локальної мережі. У i-му рядку на j-й позиції записано час проходження інформації від i-го до j-го сервера – натуральне число від 1 до 100000.

В условии всё предельно ясно описано. Нам дана матрица смежности.

Способ хранения графа в памяти, когда координаты - номер строки и столбца, а вес ребра - значение в этой "ячейке". Думаю, дальнейшее обсуждение уже выйдет за рамки настояния администрации не обсуждать посторонние вопросы. С другой стороны, в вашем распоряжении всё ещё есть Google/Yandex.