My solution:
http://ideone.com/Dnh5ZwProblem link:
http://www.spoj.com/problems/SHPATH/I am trying to implement the Dijkstra algorithm with a binary heap.
My submission always get a NZEC (non-zero exit code).
I would be happy if someone could help me to point out what's wrong in my solution, or ways to optimize it.
I already posted in the SPOJ forum but it didn't help.
Some code explanation (the code is quite long and odd):
Variables:
adj: adjacency list (graph)
last: adj list index (graph)
heap: binary heap
city: city name
visited: True if the city has been visited at least once, False otherwise
i,j,k: loop index variables
des: dest represents a city, cost represents the cost to reach it
heapidx: store the index of the heap array that contains the city, e.g if heap[3].dest = 2 then heapidx[2] = 3.
dist: the cost to reach a city
Procedures:
ReadString: seperate the first word from the second word
Div2: Some special hadling since array index start at 0
Swap: swap 2 element in the heap and update their heapidx
MinHeapify: restore heap properties
Pop: delete first element in heap
Push: push an element (a city) into the heap
Update: update a city's cost (Dijkstra) and maintaining the heap's properties
Findpath: find the shortest path