 # CIELTOMY - Editorial

SIMPLE

Backtracking

### PROBLEM

You need to find the number of different shortest paths between two given vertexes in the non-oriented weighted graph.

### EXPLANATION

Since the number of intersections is small we can simply consider all possible paths that connect 1st intersection with N-th intersection and do not pass through the same intersection twice (otherwise such path will definitely be not shortest). The easiest way to do this is to use recursive backtracking. Let’s discuss the implementation in detail.

At first we should create the so-called adjacency matrix of the town. This is a two-dimensional array A where A[i][j] denotes the length of the road between i-th and j-th intersections if this road exists and A[i][j] = 0 otherwise. Note that each road has positive length hence zeros will not lead to any ambiguity. Initially all elements in this array should be set to zero and then when we input some road of length L that connects intersections i and j we should set A[i][j] as well as A[j][i] to L since all roads are two-way.

Let us discuss at first how to iterate over all possible paths connecting 1st and N-th intersection and find their lengths. At each step we will be at some intersection and we should know what intersections we have already passed and what distance we have already walked to know how to proceed further. Hence we can create the global boolean array visited of size N where information about visited intersections will be stored. Namely, visited[k] = true if and only if we have already passed k-th intersection. Then we can create recursive routine with definition go(k, len) where k is the current intersection where we stay and len is the length of the path that we already walked. When we are staying at some intersection k we can choose arbitrary non-visited intersection j that connected with k by two-way road and walk to j incrementing len by the length of the road between k and j. Hence go(k, len) can be implemented like this:

```go(k, len)
visited[k] := true
for j=1 to N
if (not visited[j]) and (A[k][j] > 0)
go(j, len + A[k][j])
visited[k] := false
```

Note that we set visited[k] to true when we enter go(k, len) and set it to false before exit.

Current version of go(k, len) simply iterates over all paths starting from 1st intersection if we run go(1, 0). To process paths that finishing at N-th intersection we should add some lines in the beginning:

```go(k, len)
if k = N
do something with len
visited[k] := true
for j=1 to N
if (not visited[j]) and (A[k][j] > 0) then
go(j, len + A[k][j])
visited[k] := false
```

For example we can save lengths of all paths that finishes at N-th intersection in some array and then process this array to find the number of shortest paths. Having this array we can do this by two passes through it. At the first pass we can find the actual length of the shortest path and at the second pass find the number of paths having the same length as the shortest path. In fact we can do this by one pass. Let L be the current value of shortest path and C the current number of paths having length L. Then when we process some path of length len we can do the following:

```if L > len
L := len
C := 1
else if L = len
C := C + 1
```

Indeed, if L > len than all previous paths are longer than the current one hence we should set L to len and C to 1 indicating that we have currently only one shortest path. If L = len then the current path is of the same length as the shortest path so we should increase C by 1. Finally if L < len then the current path is longer than the shortest path and we simply ignore it.

Clearly in the end of the pass L will be the shortest path and C will be the number of shortest paths. Since we are now able to find the answer in one pass by the array of all paths we in fact don’t need this array anymore – we can process paths in the fly. In other words we can simply replace do something with len in the code of go(k, len) by the above code with L and C:

```go(k, len)
if k = N
if L > len
L := len
C := 1
else if L = len
C := C + 1

visited[k] := true
for j=1 to N
if (not visited[j]) and (A[k][j] > 0) then
go(j, len + A[k][j])
visited[k] := false
```

In fact when we reach N-th intersection we can stop further walking. Hence we can exit from the go routine if k = N. Another optimization that we can make is to exit from go if len > L. Indeed, even if we reach later N-th intersection len could only increase so we will ignore this path anyway. Thus the final version of go will look like:

```go(k, len)
if len > L
exit
if k = N
if L > len
L := len
C := 1
else if L = len
C := C + 1
exit

visited[k] := true
for j=1 to N
if (not visited[j]) and (A[k][j] > 0) then
go(j, len + A[k][j])
visited[k] := false
```

To get the full solution for the problem we need to init all elements of visited by false, set L to INF, C to 0 and run go(1, 0). In the end C will be the final answer. INF here is some number larger than the length of ecah path. In this problem we can safely take INF = 100. In general INF should be taken as maxC * (N - 1) + 1 where maxC is the maximal length of the road in the town.

The complexity of this algorithm is equal to the number of paths that starts at the first intersection and does not have N-th intersection as an intermediate intersection. Of course in general pruning if len > L then exit could decrease this number. But in the worst case when all pairs of intersections connected by the roads the total number of such paths equals to 2 * (N-2)! * (1/0! + 1/1! + … + 1/(N-2)!) which is approximately equals to 2 * e * (N-2)!. Here e is the base of natural logarithm. We leave this as an exercise to the reader. Thus the complexity of the algorithm in terms of N is O((N-2)!). Note that even with pruning by len the go routine can in general consider all paths. Indeed, let all roads connecting N-th intersection with other intersections has length N and all other roads have length 1. Then it is easy to see that the shortest path between 1st and N-th intersection is N on the other hand each path not having N has length <= N-2. Hence go routine with len pruning will consider all paths.

### SETTER’S SOLUTION

Can be found here.
Setter used the approach described above with one small difference. Instead of array visited he uses integer variable mask, i-th bit of which equals to visited[i] and pass this variable directly to go routine instead of making it global. See code for details.

### TESTER’S SOLUTION

Can be found here.
Tester used the approach described above.

### ALTERNATIVE APPROACH

The problem in fact can be solved in O(M + N * log N)) time. We will discuss it briefly. At first let’s find the length of shortest path from 1st intersection to every other intersection using Dijkstra’s algorithm in O(M + N * log N)) time (or in O((M + N) * log N)) time if you are using usual heap). So we are now have the array D of size N such that D[i] is the length of shortest path between 1st and i-th intersection. Now to find the number of different shortest paths to the N-th intersection one can observe that the path (V0 = 1, V1, …, VK = i) will be the shortest path from 1 to i if and only if the length of the road between Vj-1 and Vj is equal to D[Vj] - D[Vj-1] for all j from 1 to K. This allows to use dynamic programming to find the number of different shortest paths. Let F[i] be the number of shortest paths between 1st and i-th intersection. Then F = 1, F[N] is the final answer and F[i] equals to the sum of F[j] for all j such that there is a road between i and j with length D[i] - D[j]. To calculate all correctly we need to iterate over vertexes in increasing order of D[j] or use recursive DP with memoization. This is very important. If you try to code such solution with some other order of vertexes then be ready for the following test:
4 3
1 3 1
3 2 1
2 4 1
You will obtain the correct result only if you calculate values of F[] in the order: F, F, F, F.
This step of the solution requires only O(M) basic operations.

Alternatively you can combine DP step with the Dijkstra’s algorithm itself. Namely, if for some edge (u, v) of the length c you have a situation that D[v] > D[u] + c then according to the Dijkstra’s algorithm you set D[v] to D[u] + c. For calculating DP in this case simply make F[v] = F[u]. Note that according to the logic of Dijkstra’s algorithm D[u] is already correct and so F[u] is also.

Similarly to the piece of code

```    else if L = len
C := C + 1
```

of the above solution we need to do the following

```if D[v] = D[u] + c
F[v] := F[v] + F[u]
```

This gives us a solution that much easier to code than the previous one where DP was a separate step.

### RELATED PROBLEMS

8 Likes

I tried to solve this using Floyd - Warshall (because it’s really easy to implement), but got WA.

Here is my code getting WA:

``````	for ( int k = 0; k < n; ++k ) {
for ( int i = 0; i < n; ++i ) {
for ( int j = 0; j < n; ++j ) {
if ( mat[ i ][ k ] != -1 && mat[ k ][ j ] != -1 ) { // iff there is path using k
final int sum = mat[ i ][ k ] + mat[ k ][ j ];
if ( mat[ i ][ j ] == -1 || mat[ i ][ j ] > sum ) { // this path is better
mat[ i ][ j ] = sum;
if ( ( i == 0 && j == n - 1 ) || ( j == 0 && i == n - 1 ) ) cnt = 1;
} else if ( mat[ i ][ j ] == sum ) { // not better, but equally good
if ( ( i == 0 && j == n - 1 ) || ( j == 0 && i == n - 1 ) ) ++cnt;
}
}
}
}
}
``````

Is the idea incorrect or just implementation (once again)?

I solved it later using DFS, but it is N!, while Floyd Warshall is N3.

1 Like

Your solution algo was the first thought that came into my head when I read the question, but the value in cnt is just the value count[n] from this solution http://www.codechef.com/viewplaintext/1189888

Since I thought count[n] should be the answer, I’m a bit confused as to why the recursive fn was required afterwords (and what count[n] is exactly?). Maybe you can read the solution and figure it out. And then give a brief explanation The approach described by the editor gives TLE in python. Same solution gives 0.67 AC in c++.

2 Likes

It’s very interesting. In fact such solution in C++ gives 0.22 on maximal test:
http://www.codechef.com/viewsolution/1191493

But the same solution for Python get TLE on the same test with TL 6 second:
http://www.codechef.com/viewsolution/1191460

Note that it passes 6 first test files almost instantly and fails only on the neat test case described in the editorial.

Python experts, can you explain this effect?

2 Likes

hey i was using dijkstra to solve the problem.
Isn’t it just sufficient to first compute the shortest path, say min[], then for all edges incident on vertex n(say v), check their min[] values and if (min[v]+(weight of corresponding edge) == min[n]) then increment the counter for different no. of shortest paths ? I get a WA using this approach & cant understand the DP approach given in the editorial.

1 Like

My approach is to use Floyd-Warshall
ways[i][j] is the number of shortest ways from node i to j
d[i][j] is the shortest distance between node i and j

``````for k = 1 to N
for i = 1 to N
for j = 1 to N
if i == k || j == k
continue;
if d[i][k] + d[k][j] < d[i][j]
d[i][j] = d[i][k] + d[k][j]
ways[i][j] = ways[i][k] * ways[k][j]
else if d[i][k] + d[k][j] == d[i][j]
ways[i][j] += ways[i][k] * ways[k][j]
``````

Explanation
You can either pass node k or not to pass node k

If passing node k is shorter, then ways[i][j] = ways[i][k] * ways[k][j]

If passing node k is as short as not passing node k, then ways should be added.

13 Likes

It’s very bad news for me. What exactly you don’t understand in the explanation of DP approach? I was absolutely sure that all here is clear.

In fact your explanation is very close to the described DP but it is wrong. Try this test
4 6
1 2 1
1 3 2
1 4 3
2 3 1
2 4 2
3 4 1
The correct answer is 4. All shortest paths are:
1-4
1-2-4
1-3-4
1-2-3-4

I believe that your program will return 2 or may be 3.

@karan173: Yes, that approach is correct, I got AC with that idea. Be careful what you choose as states.

1 Like

@anton_lunyov: With the idea mentioned it would go something like

Go to 1 - distance 0 ways 1

Update 2 with distance 1 ways 1

Update 3 with distance 2 ways 1

Update 4 with distance 3 ways 1

Go to 2 - distance 1 ways 1

Update 3 with distance 2 ways (1 + 1)

Update 4 with distance 3 ways (1 + 1) // because 4 has 1 way and 2 has 1 way

Go to 3 - distance 2 ways 2

Update 4 with distance 3 ways (2 + 2) // because 4 has 2 ways and 3 has 2 ways

Go to 4- distance 3 ways 4
End

Ou yeah, that’s the idea where I was wrong

ways[i][j] = ways[i][k] * ways[k][j]

Thanks 1 Like

@johnathan79717 posted correct Floyd - Warshall approach

2 Likes

hey thanks anton, yeah my program prints 3 for the above case. Well i am not familiar with DP, so my bad!
and got ac by following your approach.

Glad to help very nice editorials. Even simple things have been explained thoroughly. By doing this codechef can become a very good resource one day.

4 Likes

I tried solving this problem using Djikstra + DP. The first solution I wrote http://www.codechef.com/viewsolution/1192651
computed the number of paths with length equal to shortest path after computing the distance array (containing the length of shortest path to a particular vertex i) from dijkstra’s algorithm. This solution gave WA.

In the next solution I computed F[] within the dijkstra algorithm. Solution can be found here
http://www.codechef.com/viewsolution/1193388. This solution got AC.

Logically both solutions are similar. Then why the former failed and latter passed?

1 Like

This is because you iterate over vertexes in the wrong order in the first solution. Try this test:
4 3
1 3 1
3 2 1
2 4 1
Your first solution will return 0.
I have mentioned in the editorial this example and your second solution.
Thanks for pointing this out.

Hi.
Can you please explain your DP approach “when it is a separate step” after the dijkstra algorithm.

You said that :
“F[i] equals to the sum of F[j] for all j such that there is a road between i and j with length D[i] - D[j].”

so does it mean that we have to only check that there should an edge between i and j and that should be equal to D[i]-D[j]

if ((D[i]-D[j])==originalMatrix[i][j] && originalMatrix[i][j])
… do DP …
?

@anton_lunyov

Hi i looked at code of Dij + DP (first link)
you have done :

dp = 1;
for(int i=2; i<=N; i++){
dp[i] = 0;
for(int j=0; j<graph[i].size(); j++){
if (graph[i][j].second == (distance[i]-distance[graph[i][j].first]))
dp[i] += dp[graph[i][j].first];
}

ok for i=2, graph[i][j].first can be 3,4… because it can have edges from 2 to 3.

Since it has not found the dp before, Is this method correct?

What i mean is that if you have done this thing in ascending order as suggested by anton_lunyov, would this work?
According to this, inner loop should have condition (j<i) ?

I used Floyd Warshall algorithm but wrong answer…

``````typedef struct Intersection
{
int cost;
int count;
} Intersection;
``````

Inside main, initialized my array Ints and applied FW Algo.

``````for(i = 1; i <= N; i++)
{
for(j = 1; j <= N; j++)
{
if(i != j)
{
Ints[i][j].cost = 1000;
Ints[i][j].count = 0;
}
else
{
Ints[i][j].cost = 0;
Ints[i][j].count = 1;
}
}
}

...

for(k = 1; k <= N; k++)
{
for(i = 1; i <= N; i++)
{
for(j = 1; j <= N; j++)
{
if(i != j && i != k && k != j)
{
int min_cost = min(Ints[i][k].cost + Ints[k][j].cost, Ints[i][j].cost);

if(min_cost != 1000)
{
int count = 0;

if(min_cost == Ints[i][k].cost+Ints[k][j].cost)
count += Ints[i][k].count*Ints[k][j].count;

if(min_cost == Ints[i][j].cost)
count += Ints[i][j].count;

Ints[i][j].cost = min_cost;
Ints[i][j].count = count;
}
}
}
}
}``````
//