【Atcoder】035D/Dijkstra法

こんばんは
今日はグラフ問題で、ある地点からある地点への最短距離を求めるダイクストラ法についてです。
問題はこちら
ダイクストラ法とは最小距離が確定した頂点と隣接している頂点を更新（すでに最短距離が確定した頂点は更新しない）と言うもの。

蟻本p96のように実装したら無事メモリエラー&ランタイムエラーになりました、ヒープキューを使わないとダメですね。。。

またこの問題は行きと帰りで辺の間のコストが異なるので、二種類のedgeが必要です。

##解法

from heapq import *

def dijkstra(start,node,edge):
    #始点sから各頂点への最短距離
    #node:頂点数
    #d:各頂点へのコスト(存在しないときはinf)
    #q:キュー(スタートからのコスト,頂点)
    d = [float("inf")] * node
    d[start] = 0
    #スタートをキューに入れる
    q = [(0,start)]
    
    while(len(q) != 0):
    #キューの先頭を取得
      ci,i = heappop(q)
      if(d[i] < ci):
        continue
    #キューの先頭から繋がっている頂点を探索
      for cj,j in edge[i]:
        if(d[j] > d[i] + cj):
          d[j] = d[i] + cj
          heappush(q,(d[j], j))
    return d
#入力
N,M,T = (int(x) for x in input().split())
A = list(map(int, input().split()))
#二種類のエッジ
E1 = [[] for _ in [0]*N]
E2 = [[] for _ in [0]*N]

for i in range(M):
  a,b,c = (int(x) for x in input().split())
  E1[a-1].append((c,b-1))
  E2[b-1].append((c,a-1))

go = dijkstra(0, N, E1)
back = dijkstra(0, N, E2)
ans = 0
for v in range(N):
    rem = T - (go[v] + back[v])
    ans = max(ans, rem*A[v])
print(int(ans))

ヒープキューのイメージは使ったものは捨てていく！って言うイメージなんですかね。。。
違うかも。。。