Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Олимпиада по алхимии

(Время: 1 сек. Память: 16 Мб Сложность: 53%)

В государстве алхимиков есть N населённых пунктов, пронумерованных числами от 1 до N, и M дорог. Населённые пункты бывают двух типов: деревни и города. Кроме того, в государстве есть одна столица (она может располагаться как в городе, так и в деревне). Каждая дорога соединяет два населённых пункта, и для проезда по ней требуется Ti минут. В столице было решено провести 1-ю государственную командную олимпиаду по алхимии. Для этого во все города из столицы были отправлены гонцы (по одному на город) с информацией про олимпиаду.

Напишите программу, которая посчитает, в каком порядке и через какое время каждый из гонцов доберётся до своего города. Считается, что гонец во время пути нигде не задерживается.

Входные данные

Во входном файле INPUT.TXT сначала записаны 3 числа N, M, K — количество населенных пунктов, количество дорог и количество городов (2 ≤ N ≤ 1000, 1 ≤ M ≤ 10000, 1 ≤ K ≤ N). Далее записан номер столицы C (1 ≤ C ≤ N). Следующие K чисел задают номера городов. Далее следуют M троек чисел Si, Ei, Ti, описывающих дороги: Si и Ei — номера населенных пунктов, которые соединяет данная дорога, а Ti — время для проезда по ней (1 ≤ Ti ≤ 100).

Гарантируется, что до каждого города из столицы можно добраться по дорогам (возможно, через другие населенные пункты) и то, что любые два населенных пункта соединены не более, чем одной дорогой.

Выходные данные

В выходной файл OUTPUT.TXT выведите K пар чисел: для каждого города должен быть выведен его номер и минимальное время, когда гонец может в нем оказаться (время измеряется в минутах с того момента, как гонцы выехали из столицы). Пары в выходном файле должны быть упорядочены по времени прибытия гонца, а в случае совпадения времени следует сортировать эти пары по номерам городов.

Примеры

INPUT.TXTOUTPUT.TXT
15 4 5 1
1 2 3 4 5
1 2 1
2 3 10
3 4 100
4 5 100
1 0
2 1
3 11
4 111
5 211
25 5 3 1
2 4 5
2 1 1
2 3 10
3 4 100
4 5 100
1 5 1
2 1
5 1
4 101

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]

Красноярский краевой Дворец пионеров, (c)2006 - 2017, ICQ: 151483