tz_atcoder/abc325_e.py at main · tztechno/tz_atcoder · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
###############################################
###############################################
###############################################
###############################################
###############################################
###############################################
###############################################
[atch]
import heapq
n,a,b,c=map(int,input().split())
d=[list(map(int,input().split())) for i in range(n)]
que=[]
heapq.heapify(que)
INF=1001001001001001001
dist=[INF]*n
dist[0]=0
heapq.heappush(que,(dist[0],0))
while que:
  dst,v=heapq.heappop(que)
  for nv in range(n):
    if v==nv:continue
    if dist[nv]>dst+d[v][nv]*a:
      dist[nv]=dst+d[v][nv]*a
      heapq.heappush(que,(dist[nv],nv))
for i in range(n):
  heapq.heappush(que,(dist[i],i))
  while que:
    dst,v=heapq.heappop(que)
    for nv in range(n):
      if v==nv:continue
      if dist[nv]>dst+d[v][nv]*b+c:
        dist[nv]=dst+d[v][nv]*b+c
        heapq.heappush(que,(dist[nv],nv))
print(dist[-1])
###############################################
###############################################
###############################################
###############################################
###############################################
###############################################
###############################################
###############################################
###############################################
###############################################
###############################################
###############################################
###############################################