0039. Дороги

Input file name:	roads.in
Output file name:	roads.out
Time limit:	2 s
Memory limit:	64 megabytes

Дана карта дорог города. Она задается с помощью односторонних дорог идущих из одного перекрестка в другой (двусторонние пути заданы с помощью двух односторонних). По этим дорогам требуется определить: сколькими путями можно попасть из одного перекрестка в другой? Два пути считаются различными, если они различаются последовательностью посещаемых перекрестков (один перекресток можно посещать несколько раз).

Формат входного файла

N √ число односторонних дорог. Далее в N строчках расположены через пробел перекресток начала движения и окончания движения. Номера перекрестков не превосходят 49.

Формат выходного файла

Матрица M строк по M чисел (через пробел). i-ая строка, j-ое число которой означает, каким количеством путей можно попасть из перекрестка i в перекресток j, где M – максимальный номер перекрестка, встречающийся во входном файле. Если путей бесконечное количество, выведите -1.

Пример:

roads.in	roads.out
3 0 1 1 2 2 1	0 -1 -1 0 -1 -1 0 -1 -1

Source: Petrozavodsk training camp, Summer 2002. DNK contest
Author: Denis Davydov (DNK team)

Discuss       Submit a solution