Емблема центру  www.olymp.vinnica.ua     netoi.org.ua
Центр олімпіад школярів в Iнтернеті
Likt-PMG17
м.Вiнниця


Годинник
 
SubNet

Задача Subnet

Мережа SubNet складається з N пронумерованих комп'ютерів, деякі пари з яких з'єднано провідними каналами зв'язку. Довжина кожного каналу відома. Зрозуміло, не існує каналу, що з'єднує комп'ютер сам з собою. По каналу інформація передається в обидві сторони. Між будь-якими двома комп'ютерами існує не більше одного каналу. Головний сервер мережі SubNet має номер 1. Мережні протоколи SubNet забезпечують найкоротший шлях до сервера від будь-якого з К комп'ютерів, що надсилають в даний момент часу пакети на сервер. Яка максимальна довжина тієї частини мережі, по якій проходять пакети від усіх К комп'ютерів, перш ніж потрапити на сервер?

Технічні умови: Програма читає з клавіатури цілі числа N, M, K, далі - K натуральних чисел, далі - M груп по три натуральних числа -номери з'єднаних комп'ютерів та довжина каналу між ними, що не перевищує 1000. Всі числа розділено пропусками. Мережу збудовано так, що пакети з будь-якого комп'ютера можуть дістатися до сервера.

(2<=N<=1000, 1<=M<=10000, 1<=K<=100)
N - кількість комп'ютерівв мережі,
M - кількість відрізків кабелю, що з'єднують комп'ютери попарно,
К -кількість комп'ютерів, що надсилають сигнали на сервер (введені К натуральних чисел - їх номери).


Програма виводить на екран найбільшу довжину каналів, якими, за згаданих  умов, проходять пакети від всіх К комп'ютерів на сервер.

Приклади.

Введення> 4 5 2 2 3 1 4 1 4 2 1 4 3 1 1 2 2 1 3 2
Виведення> 1

Введення> 4 5 2 2 3 1 4 1 4 2 1 4 3 1 1 2 1 1 3 1
Виведення> 0


Задача SubNet

Сеть SubNet состоит из N пронумерованных компьютеров, некоторые пары которых соединены каналами связи. Длина каждого канала известна. Естественно, не существует канала, который соединяет компьютер сам с собой. По каналу информация передается в обе стороны. Между любыми двумя компьютерами существует не больше одного канала. Главный сервер сети SubNet имеет номер 1. Сетевые протоколы SubNet обеспечивают кратчайший путь к серверу от любого из К компьютеров, которые посылают в данный момент времени пакеты на сервер. Какая максимальная длина той части сети, по которой проходят пакеты от всех К компьютеров, прежде чем попасть на сервер?.

Технические условия: Программа считывает с клавиатуры целые числа N, M, K, далее - K натуральных чисел, далее - групп по три натуральных числа - номера соединенных компьютеров и длина канала между ними, которая не превышает 1000. Все числа разделены пробелами. Сеть построена так, что пакеты от любого компьютера могут попасть на сервер.

(2<=N<=1000, 1<=M<=10000, 1<=K<=100)
N - количество компьютеров в сети,
M - количество отрезков кабеля, который соединяет компьютеры попарно,
К - количество компьютеров, которые посылают сигналы на сервер (введенные К натуральных чисел - их  номера).


Программа выводит на экран наибольшую длину каналов, по которым, при указанных условиях, проходят пакеты ото всех К компьютеров на сервер.

Примеры.

Ввод> 4 5 2 2 3 1 4 1 4 2 1 4 3 1 1 2 2 1 3 2
Вывод> 1

Ввод> 4 5 2 2 3 1 4 1 4 2 1 4 3 1 1 2 1 1 3 1
Вывод> 0



© Всеукраїнський віртуальний центр олімпіад школярів "ОЛІМП"