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