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]
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 
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.