|
1. Задача METRO (20 балів)
Ім’я вхідного файлу: METRO.DAT
Ім’я вихідного файлу: METRO.SOL
Максимальний час роботи на одному тесті: 20с
Метрополітен складається з декількох ліній метро. Усі станції метро в місті пронумеровані натуральними числами від 1 до N. На кожній лінії розташовано декілька станцій. Якщо одна і та ж станція розташована відразу на декількох лініях то вона є станцією пересадки і на цій станції можна пересісти з будь-якої лінії, яка через неї проходить, на будь-яку іншу (що знову ж таки проходить через неї).
Напишіть програму, яка по даному вам опису метрополітену визначить з яким мінімальним числом пересадок можна добратися із станції A на станцію B. Якщо цей метрополітен не сполучає усі лінії в одну систему, то може так вийти, що із станції A на станцію B добратися неможливо, в цьому випадку ваша програма повинна це визначити.
Формат вхідних даних
У вхідному файлі записано спочатку число N - кількість станцій метро в місті (2≤N≤100). Далі записано число M - кількість ліній метро (1≤M≤20). Далі йде опис M ліній. Опис кожної лінії полягає з числа Pi - кількість станцій на цій лінії (2≤Pi≤50) і Pi чисел, що задають номери станцій, через які проходить лінія (ні через яку станцію лінія не проходить двічі).
У кінці файлу записані два різних: числа A - номер початкової станції, і B - номер станції, на яку нам треба потрапити. При цьому якщо через станцію A проходить декілька ліній, то ми можемо спуститися на будь-яку з них. Так само якщо через станцію B проходить декілька ліній, то нам не важливо, по якій лінії ми приїдемо.
Формат вихідних даних
У вихідний файл виведіть мінімальну кількість пересадок, яка нам знадобиться. Якщо добратися із станції A на станцію B неможливо, виведіть у вихідний файл одне число - 1 (мінус один).
Приклад
|
METRO.DAT
|
METRO.SOL
|
|
5
2
4 1 2 3 4
2 5 3
3 1
|
0
|
|
5
5
2 1 2
2 1 3
2 2 3
2 3 4
2 4 5
1 5
|
2
|
|
10
2
6 1 3 5 7 4 9
6 2 4 6 8 10 7
3 8
|
1
|
|
4
2
2 1 2
2 3 4
1 3
|
-1
|
2. Задача “Школи” (100 балів)
Ім’я вхідного файлу: S.DAT
Ім’я вихідного файлу: S.SOL
Максимальний час роботи на одному тесті: 20с
З метою підготовки до проведення олімпіади з інформатики мер вирішив забезпечити надійним електропостачанням всі школи міста. Для цього потрібно провести лінію електропередач від альтернативного джерела електроенергії "ЕНЕРГЕТИК" до однієї з шкіл (не має значення до якої), а також з'єднати лініями електропередач деякі школи між собою. Вважається, що школа має надійне електропостачання, якщо вона напряму з’єднана з "ЕНЕРГЕТИК", або з однією з шкіл, яка має надійне електропостачання.
Відома вартість з’єднань між деякими парами шкіл. Мер міста вирішив обрати одну з двох найекономніших схем електропостачання (вартість схеми дорівнює сумі вартостей з’єднань пар шкіл).
Складіть програму SCHOOLS, яка обчислює вартість двох найекономічніших схем альтернативного енергопостачання шкіл.
Формат вхідних даних
У першому рядку вхідного файлу S.DAT розташовані два натуральних числа, відокремлених пропусками: N (3 ≤ N ≤ 100), кількість шкіл в місті, та M - кількість можливих з’єднань між ними. В кожному з наступних M рядків знаходяться по три числа: Ai, Bi, Ci, відокремлених пропусками, де Ci - вартість прокладання лінії електропостачання (1 ≤ Ci ≤ 300) від школи Ai до школи Bi (i=1,2,…,N).
Формат вихідних даних
В єдиному рядку вихідного файлу S.SOL мають міститись два натуральних числа S1 та S2, відокремлених пропусками – дві найменші вартості схем (S1≤S2). S1=S2 тільки тоді, коли існує декілька варіантів схем надійного електропостачання найменшої вартості.
Приклад
|
S.DAT
|
S.SOL
|
|
5 8
1 3 75
3 4 51
2 4 19
3 2 95
2 5 42
5 4 31
1 2 9
3 5 66
|
110 121
|
|
