Problem p03837 (python)

Fixed submission:
class Dijkstra: # 最短経路問題
    def __init__(self, route_map, start_point, goal_point=None):
        self.route_map = route_map #
        self.start_point = start_point # スタート位置
        self.goal_point = goal_point

    def execute(self):
        import heapq
        num_of_city = len(self.route_map) # ノード数
        dist = [float("inf") for _ in range(num_of_city)] # startからの距離を格納する
        prev = [float("inf") for _ in range(num_of_city)] # prev[i]:ノードiに向かう前のノード番号。これを持っておけば、goalからstartまで辿れる

        dist[self.start_point] = 0 # スタート位置までのコストは0
        heap_q = [] # 優先度つきキュー
        heapq.heappush(heap_q, (0, self.start_point)) # タプル(0,スタート位置)をheap_qに追加
        while len(heap_q) != 0:
            prev_cost, src = heapq.heappop(heap_q) # 直前にheap_qに入れたタプルから取り出す(src＝ソース)

            if dist[src] < prev_cost: # もし、スタート位置からsrcまでの距離がprev_costより小さいなら問題ないのでok
                continue

            for dest, cost in self.route_map[src].items(): # destはsrcから行ける頂点(目的地)
                if cost != float("inf") and dist[dest] > dist[src] + cost: # もし、destに有限のコストで行けて、srcからdestに行くのがスタートからの現状の最短距離になるなら、
                    dist[dest] = dist[src] + cost # 更新する
                    heapq.heappush(heap_q, (dist[dest], dest)) # 更新したのでheap_qに入れておく。次のノードに移動した時に取り出して無駄な変更がないか確認する
                    prev[dest] = src
        if self.goal_point is not None: # ゴールまでの最短経路を返す
            return self.get_path(self.goal_point, prev)
        else: # スタートから各頂点までの最短距離を格納したリストを返す
            return dist

    def get_path(self, goal, prev):  # prev[i]:ノードiに向かう前のノード番号。これを持っておけば、goalからstartまで辿れる
        global edge_num
        global used_edge
        path = [goal]
        dest = goal
        
        while prev[dest] != float("inf"): # prev[start]はfloat("inf")になり、停止する
            used_edge[edge_num[prev[dest]][dest]] += 1
            path.append(prev[dest]) # 後ろから戻っていく
            dest = prev[dest]

        return list(reversed(path)) # 逆から辿ったので順を元に戻す

import sys
input = sys.stdin.readline


N,M = map(int,input().split())
route_map = [dict() for _ in range(N)]
edge_num = [dict() for _ in range(N)]
for i in range(M): # M == エッジの数
    u, v, cost = map(int, input().split()) # cost は 辺　u -> v の重み(距離,コスト)
    u, v = u - 1, v - 1
    route_map[u][v] = cost # route_mapの第u番目のdictに{v:cost}が入る
    route_map[v][u] = cost # route_mapの第v番目のdictに{u:cost}が入る
    edge_num[u][v] = i # redge_numの第u番目のdictに{v:i}が入る
    edge_num[v][u] = i # redge_numの第v番目のdictに{u:i}が入る


used_edge = [0 for _ in range(M)]
checked_node = [[0 for _ in range(N)] for __ in range(N)]
for i in range(N-1):
    for j in range(i+1,N):
        if checked_node[i][j] != 0:
            continue
        dijkstra_result1 = Dijkstra(route_map, i, j).execute()
        for k in range(len(dijkstra_result1)-1):
            for l in range(k+1,len(dijkstra_result1)):
                checked_node[dijkstra_result1[k]][dijkstra_result1[l]] += 1
        """
        dijkstra_result2 = Dijkstra(route_map, N-1-i, N-1-j).execute()
        for k in range(len(dijkstra_result2)-1):
            for l in range(k+1,len(dijkstra_result2)):
                checked_node[dijkstra_result2[k]][dijkstra_result2[l]] += 1
        """

ans = used_edge.count(0)
print(ans)

Buggy submission (verdict: Runtime Error):
class Dijkstra: # 最短経路問題
    def __init__(self, route_map, start_point, goal_point=None):
        self.route_map = route_map #
        self.start_point = start_point # スタート位置
        self.goal_point = goal_point

    def execute(self):
        import heapq
        num_of_city = len(self.route_map) # ノード数
        dist = [float("inf") for _ in range(num_of_city)] # startからの距離を格納する
        prev = [float("inf") for _ in range(num_of_city)] # prev[i]:ノードiに向かう前のノード番号。これを持っておけば、goalからstartまで辿れる

        dist[self.start_point] = 0 # スタート位置までのコストは0
        heap_q = [] # 優先度つきキュー
        heapq.heappush(heap_q, (0, self.start_point)) # タプル(0,スタート位置)をheap_qに追加
        while len(heap_q) != 0:
            prev_cost, src = heapq.heappop(heap_q) # 直前にheap_qに入れたタプルから取り出す(src＝ソース)

            if dist[src] < prev_cost: # もし、スタート位置からsrcまでの距離がprev_costより小さいなら問題ないのでok
                continue

            for dest, cost in self.route_map[src].items(): # destはsrcから行ける頂点(目的地)
                if cost != float("inf") and dist[dest] > dist[src] + cost: # もし、destに有限のコストで行けて、srcからdestに行くのがスタートからの現状の最短距離になるなら、
                    dist[dest] = dist[src] + cost # 更新する
                    heapq.heappush(heap_q, (dist[dest], dest)) # 更新したのでheap_qに入れておく。次のノードに移動した時に取り出して無駄な変更がないか確認する
                    prev[dest] = src
        if self.goal_point is not None: # ゴールまでの最短経路を返す
            return self.get_path(self.goal_point, prev)
        else: # スタートから各頂点までの最短距離を格納したリストを返す
            return dist

    def get_path(self, goal, prev):  # prev[i]:ノードiに向かう前のノード番号。これを持っておけば、goalからstartまで辿れる
        global edge_num
        global used_edge
        path = [goal]
        dest = goal
        
        while prev[dest] != float("inf"): # prev[start]はfloat("inf")になり、停止する
            used_edge[edge_num[prev[dest]][dest]] += 1
            path.append(prev[dest]) # 後ろから戻っていく
            dest = prev[dest]

        return list(reversed(path)) # 逆から辿ったので順を元に戻す

import sys
input = sys.stdin.readline


N,M = map(int,input().split())
route_map = [dict() for _ in range(N)]
edge_num = [dict() for _ in range(N)]
for i in range(M): # M == エッジの数
    u, v, cost = map(int, input().split()) # cost は 辺　u -> v の重み(距離,コスト)
    u, v = u - 1, v - 1
    route_map[u][v] = cost # route_mapの第u番目のdictに{v:cost}が入る
    route_map[v][u] = cost # route_mapの第v番目のdictに{u:cost}が入る
    edge_num[u][v] = i # redge_numの第u番目のdictに{v:i}が入る
    edge_num[v][u] = i # redge_numの第v番目のdictに{u:i}が入る


used_edge = [0 for _ in range(M)]
checked_node = [[0 or _ in range(N)] for __ in range(N)]
for i in range(N-1):
    for j in range(i+1,N):
        if checked_node[i][j] != 0:
            continue
        dijkstra_result1 = Dijkstra(route_map, i, j).execute()
        dijkstra_result2 = Dijkstra(route_map, N-1-i, N-1-j).execute()
        for k in range(len(dijkstra_result1)-1):
            for l in range(k+1,len(dijkstra_result1)):
                checked_node[dijkstra_result1[k]][dijkstra_result1[l]] += 1
        for k in range(len(dijkstra_result2)-1):
            for l in range(k+1,len(dijkstra_result2)):
                checked_node[dijkstra_result2[k]][dijkstra_result2[l]] += 1

ans = used_edge.count(0)
print(ans)