Біржовий Вісник#3219
Брокери часто схильні перебільшувати значення чуток. Вас попросили розробити спосіб максимально швидкого поширення важливих новин або інформації серед групи брокерів.
На жаль, брокери довіряють новинам лише від своїх «надійних джерел». Це означає, що потрібно враховувати структуру їхніх контактів при поширенні новин. Кожному брокеру потрібен певний час, щоб передати інформацію кожному зі своїх колег. Ваше завдання — написати програму, яка визначить, яку людину вибрати як початкову, щоб інформацію отримали всі якнайшвидше. Тривалість вимірюється моментом, коли остання людина отримує інформацію.
Ваша програма отримуватиме дані для різних наборів брокерів. Кожен набір починається з рядка, в якому задано кількість брокерів. Далі йде по рядку для кожного брокера, які містять кількість людей, з якими він підтримує контакт, перелік цих осіб і час, необхідний, щоб передати новину кожному. Формат для кожного рядка брокера наступний: рядок починається з числа контактів (), далі йдуть пар цілих чисел — по одній для кожного контакту. Кожна пара складається спочатку з номера контакту (наприклад, «1» означає особу номер один у цьому наборі), потім через пробіл — часу в хвилинах, необхідного на передачу новини цій особі. Додаткових розділових знаків або спеціальних правил форматування пробілів немає.
Для кожного набору даних ваша програма повинна вивести єдиний рядок, що містить номер особи, яка забезпечує найшвидшу передачу повідомлення, та за скільки хвилин остання людина дізнається новину, починаючи з цієї особи (час у цілих хвилинах).
Кожна особа пронумерована від 1 до кількості брокерів у наборі. Час передачі повідомлення становить від до хвилин (включно), а кількість контактів — від до одного меншого, ніж кількість брокерів. Кількість брокерів коливається від до . Вхідні дані завершуються набором із (нуль) осіб.
Може трапитися, що у вашій програмі буде мережа контактів, у якій деякі особи є недосяжними, тобто окремі люди не можуть отримати повідомлення. Якщо програма виявить таку розірвану мережу, просто виведіть повідомлення "disjoint". Зауважте, що час передачі повідомлення від особи A до особи B не обов'язково збігається з часом передачі від B до A, якщо така передача взагалі можлива.
Приклад 1