Submission #8641310

---

Source Code Expand

#2つ目のやり方
import heapq
    
def dijkstra(s):
    d = [float("inf")]*N
    BOOL = [0]*N
    d[s] = 0
    BOOL[s] = 1
    P = []
    for e in edge[s]:
        heapq.heappush(P,e)
    while len(P) > 0:
        cur = heapq.heappop(P)
        if BOOL[cur[1]] == 1:
            continue
        v = cur[1]
        d[v] = cur[0]
        BOOL[v] = 1
        for e in edge[v]:
            if BOOL[e[1]] == 0:
                heapq.heappush(P,[e[0]+d[v],e[1]])
    return d
N,M,T = map(int,input().split())
A = list(map(int,input().split()))
ans = 0
edge = [[] for i in range(N)]
L = []
for i in range(M):
    a,b,c = map(int,input().split())
    L.append([a,b,c])
    edge[a-1].append([c,b-1])
iki = dijkstra(0)
edge = [[] for i in range(N)]
for i in range(M):
    edge[L[i][1]-1].append([L[i][2],L[i][0]-1])
kaeri = dijkstra(0)
for i in range(N):
    ans = max(ans,(T-iki[i]-kaeri[i])*A[i])
print(ans)

Submission Info

Judge Result