Человек Рассеянный
(Время: 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.TXT | OUTPUT.TXT |
1 | 3 5 2
0 1 1
1 0 1
0 2 1
2 0 1
1 2 1 | 2/1
2/1
2/1 |
2 | 3 3 3
0 1 1
1 2 1
2 0 1 | Impossible
6/2
Impossible |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
|