Well, NZEC problem yet again.
I'm solving this problem : spoj.pl/problems/HIGHWAYS/
I'm getting NZEC, but my program is also slow. So i would appreciate any suggestions.
Here is my code : Dijkstra's algo + heapq (priority_queue)
#!/usr/bin/python
import heapq
class priority_queue(object) :
def __init__(self) :
self.arr = []
def push(self, elem) :
heapq.heappush(self.arr, elem)
def pop(self) :
return heapq.heappop(self.arr)
def empty(self) :
return len(self.arr) == 0
def main() :
n, m, start, end = [int(x) for x in raw_input().split()]
visited, dist = [False] * n, [100000000] * n
Q = priority_queue()
grid = {}
for i in range(m) :
a, b, c = [int(x) for x in raw_input().split()]
if not a-1 in grid : grid[a-1] = []
if not b-1 in grid : grid[b-1] = []
grid[a-1].append((b-1, c))
grid[b-1].append((a-1, c))
dist[start-1] = 0
Q.push((0, start-1))
while not Q.empty() :
cdist, curr = Q.pop()
visited[curr] = True
for i in grid[curr] :
node, val = i
if visited[node] : continue
if dist[curr] + val < dist[node] :
dist[node] = dist[curr] + val
Q.push((dist[node], node))
if dist[end-1] == 100000000 : print 'NONE'
else : print dist[end-1]
if __name__ == '__main__' :
test = input()
for i in range(test):
main()
