CIELTOMY - Editorial

PROBLEM LINK

Practice
Contest

DIFFICULTY

SIMPLE

PREREQUISITES

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] = 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[1], F[3], F[2], F[4].
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

Social Constraints (UVA 11742)
Getting in Line (UVA 216)
The N Queens Puzzle Revisited (Codechef J3)

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;
					}
				}
			}
		}
	}

or link to sumbission…

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

The approach described by the editor gives TLE in python. Same solution gives 0.67 AC in c++.

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]

The answer is ways[1][N]

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.

14 Likes

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

I used Floyd Warshall algorithm but wrong answer…

Please help.

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

Inside main, initialized my array Ints[11][11] 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;
				}
			}
		}
	}
}

Do we actually need DP after Dijkstra? I tried modifying dijsktra also a bit but getting wrong answer. Any help would be greatly appreciated.
I am using STL priority queue. Following is the full code:


int *distanceFromStartNode;
struct closest_node{
    bool operator()(const int node1, const int node2){
        return distanceFromStartNode[node1]>distanceFromStartNode[node2];
    }
};
int main(){
	int t;
	for( cin>>t; t>0; t--){
		int graph[11][11];
		int numNodes; cin>>numNodes;

		int pathCount[11];
		distanceFromStartNode = new int[11];
//init arrays
		for(int i=1; i<=numNodes; i++){
			pathCount[i] = 0;
			distanceFromStartNode[i] = 10000;
			for(int j=1; j<=numNodes; j++){
				graph[i][j] = 10000;
			}
		}

//input to arrays
		int numRoads; cin>>numRoads;
		for(int i=0; i<numRoads; i++){
			int a, b, d;
			cin>>a>>b>>d;
			graph[b][a] = graph[a][b] = d;
		}

//processing
		priority_queue<int, vector<int>, closest_node > Q;//create priority queue Q which will return node closest to start_node
		for(int node=1; node<=numNodes; node++)//put all the node in Q
			Q.push(node);
		distanceFromStartNode[1]=0;
		pathCount[1] = 1;

		while(!Q.empty()){//for each level
			int curNode = Q.top(); Q.pop();
			for(int adjNode=1; adjNode<=numNodes; adjNode++){//foreach adj. node
				if(curNode!=adjNode){
					int curDist = distanceFromStartNode[curNode]+graph[curNode][adjNode];
					if(distanceFromStartNode[adjNode] > curDist){
						distanceFromStartNode[adjNode] = curDist;
						pathCount[adjNode] = pathCount[curNode];
					}else if(distanceFromStartNode[adjNode] == curDist){
						pathCount[adjNode] += pathCount[curNode];
					}
				}
			}
		}
		cout<<pathCount[numNodes]<<endl;
	}
	delete[] distanceFromStartNode;
	getchar();
	return 0;
}

Thanks
Monish

#include
#include
#include
#include
#include
#include

using namespace std;

const int MaxN = 100;

int n, m, t;
int dist[MaxN];
multimap<int, int> H;
vector<pair<int, int> > V[MaxN];
int ways[MaxN];

void dijkstra(int source)
{
    for (int i = 1; i <= n; i++) dist[i] = -1;
    dist[source] = 0;

    H.insert(make_pair(0, source));

    while (!H.empty())
    {
        multimap<int, int>::iterator it = H.begin();
        int v = (*it).second, d = (*it).first;

        H.erase(it);

        for (int i = 0; i < V[v].size(); i++)
        {
            int tmp = d + V[v].at(i).first, j = V[v].at(i).second;

            if (tmp < dist[j] || dist[j] < 0) 
              {H.insert(make_pair(tmp, j)); dist[j] = tmp; ways[j] = ways[v];}

            else if (tmp == dist[j]) ways[j] += ways[v];
        }
    }
}

inline void clear_vector()
{
    for (int i = 0; i < MaxN; i++) V[i].clear();
}


int main()
{
    cin.sync_with_stdio(0);
    cin >> t;

    while (t--)
    {
        clear_vector();
        memset(ways, 0, sizeof(ways));
        H.clear();

        cin >> n >> m;
        while (m--)
        {
            int u, v, cost;
            cin >> u >> v >> cost;

            V[u].push_back(make_pair(cost, v));
        }

        ways[1] = 1;
        dijkstra(1);

        printf("%d\n", ways[n]);
    }
    return 0;
}

http://www.codechef.com/viewsolution/1685377
My code is getting WA but it works for your example with 4 ways, and it works for the example where the edges aren’t in order.There’s a link to my solution if anybody could help me i’d be really glad.Also works for a lot of examples i tried offline.

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 :slight_smile:

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

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 :wink:

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 :slight_smile:

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.