Submission #8640764

---

Source Code Expand

#一つ目のやり方

N,M,T = map(int,input().split())
A = list(map(int,input().split()))
cost = []
ans = 0
for i in range(N):
    L = [float('inf') for i in range(N)]
    cost.append(L)
for i in range(M):
    a,b,c = map(int,input().split())
    cost[a-1][b-1] = c
cost_iki = [float('inf')]*N
cost_kaeri = [float('inf')]*N
cost_oufuku = [float('inf')]*N
BOOL_iki = [0]*N
BOOL_kaeri = [0]*N
cost_iki[0] = 0
cost_kaeri[0] = 0
BOOL_iki[0] = 1
BOOL_kaeri[0] = 1
for i in range(N):
    if cost[0][i] != float('inf'):
        cost_iki[i] = cost[0][i]
    if cost[i][0] != float('inf'):
        cost_kaeri[i] = cost[i][0]
while BOOL_iki != [1]*N:
    temp = 0
    temp_cost = float('inf')
    for i in range(N):
        if BOOL_iki[i] != 1:
            if temp_cost >= cost_iki[i]:
                temp = i
                temp_cost = cost_iki[i]
    BOOL_iki[temp] = 1
    for i in range(N):
        cost_iki[i] = min(cost_iki[i],cost_iki[temp]+cost[temp][i])
while BOOL_kaeri != [1]*N:
    temp = 0
    temp_cost = float('inf')
    for i in range(N):
        if BOOL_kaeri[i] != 1:
            if temp_cost >= cost_kaeri[i]:
                temp = i
                temp_cost = cost_kaeri[i]
    BOOL_kaeri[temp] = 1
    for i in range(N):
        cost_kaeri[i] = min(cost_kaeri[i],cost_kaeri[temp]+cost[i][temp])
for i in range(N):
    cost_oufuku[i] = cost_iki[i]+cost_kaeri[i]
for i in range(N):
    ans = max(ans,(T-cost_oufuku[i])*A[i])
print(ans)

Submission Info

Judge Result