Подскажите, пожалуйста, как решить.

Дан неориентированный взвешенный граф. Вроде какой-то динамикой можно посчитать количество кратчайших путей из v в u для всех u, предварительно запустив дейкстру из v. Вроде это можно делать даже параллельно с дейкстрой как-то. Как именно? :)

Взято из задачи G отсюда: http://codeforces.com/gym/100371/attachments/download/2258/2014-zimnyaya-shkola-po-programmirovaniu-harkov-dyen-1-ye-kapun-vysshaya-liga-ru.pdf