ABC 035 D トレジャーハント

競技プログラミング

qiita.com

続き。

atcoder.jp

考えたこと

1 に戻ってくる最短経路をTから引いて、経路内で最も単位あたりの獲得金額が高い頂点を探して、そこで最大限いたことにするというものを実装してみた。結果的にダメだった。8割くらいACしたけど、残り2割がダメだった。

一応経過ということで、明日解答を追加する。

from collections import defaultdict
import queue
push = queue.heappush
pop = queue.heappop
INF = 10**7
G = defaultdict(list)
N, M, T = map(int, input().split())
A = list(map(int, input().split()))
check = dict()
for i in range(M):
    a, b, c = map(int, input().split())
    # 有向グラフ
    G[a-1].append((b-1, c))
    if b == 1:
        check[a-1] = c

def dijkstra(s):
    q = []
    d = [INF] * N
    p = [-1] * N
    d[s] = 0
    push(q, (0, s))

    while q:
        cost, v = pop(q)
        # 既に q から取り出したものの方が低い
        if d[v] < cost:
            continue
        for to, tmpcost in G[v]:
            if d[to] > d[v] + tmpcost:
                d[to] = d[v] + tmpcost
                p[to] = v
                push(q, (d[to], to))
    return (d, p)

def get_path(t, p):
    path = []
    while t != -1:
        path.append(t)
        t = p[t]
    return path

rd, rp = dijkstra(0)
ans = -1
for c in check.keys():
    rd[c] += check[c]
    path = get_path(c, rp)
    maxv = -1
    for pp in path:
        maxv = max(maxv, A[pp])
    ans = max(ans, (T-rd[c])*maxv)

print(max(ans, T*A[0]))