Editorial for COCI '08 Contest 3 #6 Najkraci

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

A small modification to Dijkstra's shortest path algorithm allows us to find roads that are part of shortest paths from a source city.

For a fixed city $C$ ~C~, the roads form a directed acyclic graph (DAG) and we can use dynamic programming to calculate:

$to(v)$ ~to(v)~, the number of paths from city $C$ ~C~ to city $v$ ~v~;
$from(v)$ ~from(v)~, the number of paths from city $v$ ~v~ to any other city.

To calculate the values of $to(v)$ ~to(v)~ we use the formulas:

$to(C) = 1$ ~to(C) = 1~
$to(v) = \sum to(u)$ ~to(v) = \sum to(u)~, for each city $u$ ~u~ such that edge $(u, v)$ ~(u, v)~ is part of the DAG.

To calculate the values of $from(v)$ ~from(v)~ we use the formula:

$from(v) = 1 + \sum from(w)$ ~from(v) = 1 + \sum from(w)~, for each city $w$ ~w~ such that edge $(v, w)$ ~(v, w)~ is part of the DAG.

The values of $to(v)$ ~to(v)~ are calculated in order in which Dijkstra's algorithm processes the vertices, while $from(v)$ ~from(v)~ is calculated in reverse order.

Knowing these values, we can calculate how many shortest paths from $C$ ~C~ to some other city contains a road $R = (A, B)$ ~R = (A, B)~.

If road $R$ ~R~ is not part of the DAG, then this amount is zero. Otherwise it is $to(A) \cdot from(B)$ ~to(A) \cdot from(B)~. The total number of shortest paths containing road $R$ ~R~ is calculated as the sum of these products for every starting city $C$ ~C~.

Comments

There are no comments at the moment.