abc 035 d (python)

ダイクストラ法の問題
この問題は道路を片方向にしか通れないので、１からｋまでの最短路とｋから1までの最短路は別に求める必要がある。

import sys
input = sys.stdin.readline
n,m,t = map(int,input().split())
a = list(map(int,input().split()))
a = tuple(a)
ed = [[] for i in range(n)]
re = [[] for i in range(n)]
for i in range(m):
  x,y,z = map(int,input().split())
  ed[x-1].append([z,y-1])
  re[y-1].append([z,x-1])

import heapq
def dijkstra_heap(s,edge):
    #始点sから各頂点への最短距離
    d = [10**10] * n
    used = [True] * n
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d
  
chk = dijkstra_heap(0,ed)
cc = dijkstra_heap(0,re)
ans = a[0]*t
for i in range(1,n):
  p = (t-chk[i]-cc[i])*a[i]
  ans = max(ans,p)
print(ans)