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

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


 

Человек Рассеянный

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

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

В его сказке N городов, некоторые из них соединены железнодорожными маршрутами. Каждый маршрут имеет некоторую стоимость проезда. Если Человек Рассеянный проезжает по некоторому маршруту, он выплачивает его стоимость.

Совершенно случайно, замучившись поднимать Шалтая-Болтая, из другой сказки сюда попали Вся Королевская Конница и Вся Королевская Рать. Быстро сориентировавшись на месте, они решили найти Человека Рассеянного и вернуть его домой.

Чтобы начать поиски, им необходимо собрать некоторую статистику про путешествия Человека Рассеянного. Пока им известно только то, что он начал путешествие в городе номер 1 и проехал на поезде K раз. Теперь они хотят для каждой станции узнать, сколько в среднем денег потратил Человек Рассеянный, если по истечении K поездок он оказался на этой станции.

Рассмотрим все возможные способы, которыми он мог попасть на данную станцию. Просуммируем затраты по всем таким путям и разделим их на количество этих путей. Таким образом, для станции i мы получим величину Ai – средняя сумма денег, потраченная на путешествие до станции i за K поездок.

Даны стоимости железнодорожных маршрутов между городами и число K. Для каждой станции найдите среднюю сумму денег, потраченную на путешествие до этой станции за K поездок.

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

В первой строке входного файла INPUT.TXT находятся три числа: N (2 ≤ N ≤ 100), M (N ≤ M ≤ 10000) и K (1 ≤ K ≤ 20).

Далее следует M строк, в каждой из которых находится описание одного железнодорожного маршрута. В каждой такой строке находятся 3 целых числа Si, Ei, Ci, обозначающие, что из города с номером Si в город с номером Ei ведет маршрут стоимостью Ci. Города нумеруются с нуля. Все маршруты ориентированные. Все стоимости маршрутов неотрицательны и не превосходят 1000. Из любого города ведет хотя бы один маршрут.

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

В выходной файл OUTPUT.TXT для каждой станции выведите требуемое число в виде дроби, по одному на каждой строке. Если до какой-то станции невозможно доехать, то следует вывести Impossible вместо дроби. Знаменатель опускать нельзя даже в том случае, когда он равен единице. Длина каждой строки не должна превышать 1000.

Примеры

INPUT.TXTOUTPUT.TXT
13 5 2
0 1 1
1 0 1
0 2 1
2 0 1
1 2 1
2/1
2/1
2/1
23 3 3
0 1 1
1 2 1
2 0 1
Impossible
6/2
Impossible

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

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


 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 ЕГЭ по информатике
 Тренировочные олимпиады
 Личные олимпиады
 Командные олимпиады
 Первая командная олимпиада
 Вторая командная олимпиада
 Третья командная олимпиада
 Четвертая командная олимпиада
 A. Алфавит для слепых
 B. Квадраты
 C. Офицеры
 D. Выражение
 E. Сапер
 F. Человек Рассеянный
 G. Строительство города
 H. Безопасный пароль

Красноярский краевой Дворец пионеров, (c)2006 - 2024, ИНН 246305493507, E-mail: admin@acmp.ru



Заказать эвакуатор в ярославле.   https://w-dprint.ru рекламно производственная компания москва и область.