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.
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] = 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]
Woo! I am actually trying the algo described towards the end of the editorial. But it’s giving WA for some reason.
I believe that your Dijkstra algorithm is incorrect.
It seems that you assume that because of such tricky compare function
your priority queue will change when you change some distance. But it is implemented as an ordinary heap on vector so the only way you can reconstruct it is to use push().
To help you with debugging I can suggest the following test
4 6
1 2 1
1 3 2
1 4 3
2 3 1
2 4 2
3 4 1
The answer is 4.
I did not check your solution for this test.
So if it will pass then sorry 
1 Like
Thanks anton_lunyov, the test case you provided is failing. Heap has to be rebuild before pop() from PQ. Following are the changes I made if anyone interested:
//processing
vector<int> 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_back(node);
make_heap(Q.begin(), Q.end(), closest_node());
while(!Q.empty()){
make_heap(Q.begin(), Q.end(), closest_node());
int curNode = Q.front(); pop_heap(Q.begin(), Q.end(), closest_node()); Q.pop_back();
</pre>
Actually, the way you fix this ruined all the advantages of using priority queue here
The main advantage is the time complexity that should be O((V+E) log E). In your code it is something like O(V^2 + E) because of these rebulidings.
The correct way is to make priority queue of pairs of the form (-distance[u], u) and after each successful relaxation push the pair (-distance[u], u) to the queue. In this way we can have several pairs for the same vertex in the queue but this is not bad since we simply ignore the pairs for which the first element is not the actual distance… (lack of space)
Of course in this problem time complexity is not important but if you try some real problems having over 100000 vertexes and edges you will get TLE with such solution.