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