ABC 035 D トレジャーハント(2)
昨日の続きです。
昨日は、考えでは、ダメなことがわかったので、解答を見た。考えは、だいぶ似ていた。
ただし、最短経路上の単位獲得金額がでかい都市を探す必要がなかった。すべての都市を往復することで、経路上の単位獲得金額がでかい都市を特定することができるので、大丈夫みたいだ。
都市の往復をするには、辺を逆に貼ることで、帰りの移動時間を計算できる。
以下、解答。
```python
from collections import defaultdict
import queue
push = queue.heappush
pop = queue.heappop
INF = 10**20
G1 = defaultdict(list)
# 逆方向
G2 = defaultdict(list)
N, M, T = map(int, input().split())
A = list(map(int, input().split()))
for i in range(M):
a, b, c = map(int, input().split())
G1[a-1].append*1
G2[b-1].append*2
def dijkstra(s, G):
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
push(q, (d[to], to))
return d
# 行き
d1 = dijkstra(0, G1)
# 帰り
d2 = dijkstra(0, G2)
ans = -1
for i in range(N):
ans = max(ans, (T-(d1[i]+d2[i]))*A[i])
print(ans)
```
AC。スッキリしたぜ。
