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 
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 
1 Like
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 
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 …
?
Hi i looked at code of Dij + DP (first link)
you have done :
dp[1] = 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[3] 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) ?
Did a silly mistake in the question… While getting the input I was setting only Ints[Ai][Bi], the solution works correctly after setting Ints[Ai][Bi] and Ints[Bi][Ai]