提出 #6215481

---

ソースコード 拡げる

"""
start -> x -> hokora -> x -> goal
各区間が、指定された対戦回数の中で最短経路
"""
import sys
input = sys.stdin.readline
import numpy as np

R,C,K = map(int,input().split())
S = 'T' * (C+2)
for _ in range(R):
  S += 'T' + input().rstrip() + 'T'
S += 'T' * (C+2)
L = len(S)

INF = 10 ** 15
  
start = S.find('S')
goal = S.find('G')
hokora = S.find('C')

def dijkstra(start):
  # 接触する敵、場所
  dist = [[INF] * L for _ in range(K+1)]
  q = [(0,start)]
  d = 0
  dist[0][start] = 0
  move = (1,-1,C+2,-C-2)
  while q:
    d += 1
    qq = []
    for k,x in q:
      for dx in move:
        x1 = x+dx
        k1 = k
        c = S[x1]
        if c == 'T':
          continue
        if c == 'E':
          k1 += 1
          if k1 > K:
            continue
        if dist[k1][x1] < INF:
          continue
        dist[k1][x1] = d
        qq.append((k1,x1))
    q = qq
  return np.array(dist, dtype=np.int64)

d1 = dijkstra(start)
d2 = dijkstra(goal)
d3 = dijkstra(hokora)
# 共通の地点の補正
enemy = [i for i,c in enumerate(S) if c == 'E']
d2[:K,enemy] = d2[1:,enemy]
d2[K,enemy] = 0
d3[:K,enemy] = d3[1:,enemy]
d3[K,enemy] = 0

def merge(d1,d2):
  d = np.full((2*K+1,L), INF, dtype=np.int64)
  # d[n] = min(a+b = n) d1[a] + d2[b]
  for a in range(K+1):
    d[a:a+K+1] = np.minimum(d[a:a+K+1], d1[a] + d2)
  return d[:K+1]

d = merge(d1,d2)
d = merge(d,2*d3)

answer = d.min()
if answer == INF:
  answer = -1
print(answer)

提出情報

ジャッジ結果