Задача №113268. Кратчайшие пути
Дорожная сеть некоторой страны состоит из N городов и M дорог, по которым можно двигаться только в одном направлении. Города пронумерованы целыми числами от 1 до N . Для каждой дороги известна её длина.
Путём из города A в город B называется такая последовательность дорог, в которой первая дорога последовательности ведёт из города A , каждая следующая дорога выходит из города, в который ведёт предыдущая дорога, а последняя дорога ведёт в город B . Длиной пути будем называть сумму длин дорог, из которого он состоит. Путь из города A в город B называется кратчайшим, если не существует другого пути из города A в город B , у которого длина меньше.
Ваша задача заключается в том, чтобы для каждой дороги посчитать количество различных кратчайших путей, которым эта дорога принадлежит, по модулю 1 000 000 007 .
В первой строке входного потока заданы два целых числа N и M "— количество городов и дорог в стране ( 1 ≤ N ≤ 1500 , 1 ≤ M ≤ 5000 ). Следующие M строк содержат описание дорог. Каждая дорога описывается тремя целыми числами: x i "— номер города, из которого ведёт данная дорога, y i "— номер города, в который ведёт данная дорога и w i "— длина дороги ( 1 ≤ x i , y i ≤ N , x i ≠ y i , 1 ≤ w i ≤ 10 000 ).
Выведите M чисел, каждое на отдельной строке, "— для каждой дороги количество различных кратчайших путей, которым принадлежит эта дорога, по модулю 1 000 000 007 . Порядок этих чисел должен соответствовать порядку дорог во входном потоке.
Решения, работающие для ограничений N ≤ 15 и M ≤ 30 , будут оцениваться из 30 баллов. Решения, работающие для ограничений N ≤ 300 и M ≤ 1000 , будут оцениваться из 60 баллов.
4 3 1 2 5 2 3 5 3 4 5
3 4 3
4 4 1 2 5 2 3 5 3 4 5 1 4 8
2 3 2 1
5 8 1 2 20 1 3 2 2 3 2 4 2 3 4 2 3 3 4 5 4 3 5 5 4 20
0 4 6 6 6 7 2 6