Отправляет email-рассылки с помощью сервиса Sendsay

Информат - алгоритмическое и математическое мышление

Рассылка закрыта

При закрытии подписчики были переданы в рассылку "физика YES" на которую и рекомендуем вам подписаться.

Вы можете найти рассылки сходной тематики в Каталоге рассылок.

←   Март 2006   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
Автор
ss77_ss77@mail.ru

Статистика

1.523 подписчиков
+1 за неделю
←   Все выпуски   →

Конкурсы и Олимпиады по Машинному программированию (КОМП) Задача 4


Сегодня представляю задачу уровня 4. Для тех, кто не смог пройти этот уровень, остальные задачи так и останутся не известными. В следующих рассылках будут разборы задач уровня 3 и 4.
 

Задача уровня 4

НУИНУ

Здание НУИНУ (Научный Универсальный Институт Необыкновенных Услуг. Этот институт фигурирует в фильме "Чародеи", снятый по мотивам книги Стругацких "Понедельник начинается в субботу". Там как раз и возникла проблема с выходом посетителя из здания института) представляет собой залы, соединённые коридорами.

Найти нужный зал с непривычки очень сложно, так же сложно выйти из института. Чтобы посетители не затруднялись выйти, достаточно в каждом зале повесить табличку "Выход" над коридором, ведущим к выходу. Поскольку может оказаться, что путей к выходу несколько, было решено выбирать самый короткий. Длины коридоров отличаются не значительно и их не учитываем. Если оказывается, что коротких путей из какого-то зала несколько выбираем любой, но один.

Задача

По заданной схеме коридоров укажите, где нужно повесить таблички "Выход".

Техническое задание

Все залы пронумерованы натуральными числами до 10000.

Все коридоры пронумерованы натуральными числами до 10000.

Соединение --- тройка: номер первого зала, номер коридора, номер второго зала. Соединение показывает, какие залы соединяет коридор. Один коридор может соединять только два зала. Из зала может выходить множество коридоров. По коридорам можно двигаться в любую сторону. Выход расположен в первом зале, в нем табличка не нужна.

Во входной поток подаётся:
N --- Число соединений
Соединение 1
...
Соединение N
В выходной поток нужно выдать список развешанных табличек в виде:
M --- Количество табличек
Зал1 коридор1
...
ЗалM коридорM

Т.е. указывается зал и коридор, над которым висит табличка "Выход" в этом зале.

Пример

6
1 10 10
1 20 1000
1 30 100
10 40 1000
10 50 100
100 60 1000

Ответ:
3
10 10
100 30
1000 20



Автор: Пупышев Вячеслав Викторович   
e-mail: pvv@uni.udm.ru   
Web: http://colymp.da.ru   
В избранное