Problem:


 Princess in Danger 

 お姫様の危機 

English text is not available in this practice contest.

ある貧乏な国のおてんばで勇敢なお姫様が，政略結婚のため別の国に嫁ぐことになった．ところが，お姫様を亡き者としようとしている悪漢に嫁ぎ先への道中で襲われお姫様が大けがをしてしまい，近くの病院に搬送された．ところが，悪漢はお姫様は確実に亡き者とするため特殊な毒を使っていた．そのため，お姫様を助けるには本国から特別な薬と冷凍された肉親の血液を大急ぎで運ばなければならなくなった．

この血液は冷凍状態で輸送されるのだが，鮮度を保つため，前回の冷凍から最大 M 分以内に血液冷凍施設で再冷凍しなければならない．しかし，冷凍施設が設置されている場所は数カ所しかない．

血液は，十分に冷凍した状態から，再冷凍なしで M 分の間無事である．再冷凍しなくてすむ残り時間が S 分のときに，T 分間冷凍しないで輸送した場合，再冷凍しなくてすむ残り時間は S - T 分となる．再冷凍しなくてすむ残り時間は，再冷凍することにより，最大 M 分まで回復する．血液の再冷凍にかかる時間は，どれだけ冷凍するかに依存する．血液を冷凍施設で，1分冷凍するごとに再冷凍しなくてすむ残り時間は1分回復する．

本国の首都を出発する時点の，血液を再冷凍しなくてすむ残り時間はM分である．

お姫様の従者であるあなたは，大切な主君の命を救うため，本国の首都からお姫様が搬送された病院まで血液の鮮度を保ったまま輸送するための経路を計算しなければならない．そう，あなたの使命は，本国の首都からその病院への最短経路を割り出し，その最短時間を求めることである．

Input

入力は，複数のデータセットより構成される．各データセットの最初の行には，6 つの非負の整数 N(2 ≦ N ≦ 100)，M(1 ≦ M ≦ 100)，L(0 ≦ L ≦ N - 2)，K，A(0 ≦ A ＜ N)，H(0 ≦ H ＜ N) が与えられる．これらはそれぞれ，町の数，再冷凍を行うまでの制限時間，冷凍施設のある町の数，町と町を直接結ぶ道路の数，本国の首都を表す番号，お姫様が搬送された病院のある町の番号を表す．本国の首都とお姫様が搬送された病院は，異なる町である．なお，町には 0 〜 N-1 までの番号がそれぞれ割り当てられているものとする．続く行には，L 個の非負の整数が 1 つの空白で区切られて与えられる．これらは，冷凍施設がある町の番号を表す．なお，本国の首都とお姫様が搬送された病院はこのリストには含まれないが，冷凍施設があるものと考えて良い．続く K 行では，町と町を結ぶ道路の情報が与えられる．その第 i 行目では，3 つの非負の整数 X ，Y ，T が 1 つの空白で区切られて与えられ，これは町 X と町 Y を直接結ぶ道があり，移動には時間 T を要するということを表す．なお，この道は双方向に通行可能である．また，町Xと町Yを直接結ぶ道は高々一つしか無い．

入力は N = M = L = K = A = H = 0 の時に終了し，これはデータセットに含まれない．

Output

各データセットについて，鮮度を保ったまま血液を届けることができる最短時間を出力せよ．もし届けることができない場合には "Help!" と出力せよ．

Sample Input

2 1 0 1 0 1
0 1 2
3 1 1 2 0 1
2
0 2 1
1 2 1
3 2 1 2 0 1
2
0 2 1
1 2 1
4 4 1 4 1 3
2
0 1 2
1 2 4
0 2 1
3 0 3
5 3 2 6 0 3
1 2
2 1 2
1 0 1
3 4 1
2 4 1
4 1 2
2 0 2
5 4 2 6 0 3
1 2
4 2 4
2 1 2
4 3 1
0 1 5
1 4 2
2 0 3
0 0 0 0 0 0

Output for the Sample Input

Help!
3
2
10
5
12



Sample input:
2 1 0 1 0 1
0 1 2
3 1 1 2 0 1
2
0 2 1
1 2 1
3 2 1 2 0 1
2
0 2 1
1 2 1
4 4 1 4 1 3
2
0 1 2
1 2 4
0 2 1
3 0 3
5 3 2 6 0 3
1 2
2 1 2
1 0 1
3 4 1
2 4 1
4 1 2
2 0 2
5 4 2 6 0 3
1 2
4 2 4
2 1 2
4 3 1
0 1 5
1 4 2
2 0 3
0 0 0 0 0 0


Sample output:
Help!
3
2
10
5
12

Submission status: Wrong Answer

Solution code:

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353
dd = [(0,-1),(1,0),(0,1),(-1,0)]
ddn = [(0,-1),(1,-1),(1,0),(1,1),(0,1),(-1,-1),(-1,0),(-1,1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    while True:
        N,M,L,K,A,H = LI()
        if N == 0:
            break
        S = set()
        if L > 0:
            S = set(LI())
        else:
            input()
        e = collections.defaultdict(list)
        for _ in range(K):
            a,b,d = LI()
            e[a].append((b,d))
            e[b].append((a,d))

        def search(s):
            d = collections.defaultdict(lambda: inf)
            d[(-M,s)] = 0
            q = []
            heapq.heappush(q, (0, -M, s))
            v = collections.defaultdict(bool)
            while len(q):
                k, m, u = heapq.heappop(q)
                if v[(m,u)]:
                    continue
                for mm in range(m,1):
                    v[(mm,u)] = True

                for uv, ud in e[u]:
                    if ud > -m or v[(m+ud,uv)]:
                        continue
                    vd = k + ud
                    vm = m+ud
                    if uv in S:
                        vm = -M
                    if d[(vm,uv)] > vd:
                        for mm in range(vm,1):
                            d[(mm,uv)] = vd
                        heapq.heappush(q, (vd, vm, uv))

            return d

        d = search(A)
        r = inf
        for k in list(d.keys()):
            if k[1] == H and r > d[k]:
                r = d[k]
        if r == inf:
            rr.append('Help!')
        elif r <= M:
            rr.append(r)
        else:
            rr.append(r*2-M)

    return '\n'.join(map(str,rr))


print(main())

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353
dd = [(0,-1),(1,0),(0,1),(-1,0)]
ddn = [(0,-1),(1,-1),(1,0),(1,1),(0,1),(-1,-1),(-1,0),(-1,1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    while True:
        N,M,L,K,A,H = LI()
        if N == 0:
            break
        S = set()
        if L > 0:
            S = set(LI())
        else:
            input()
        e = collections.defaultdict(list)
        for _ in range(K):
            a,b,d = LI()
            e[a].append((b,d))
            e[b].append((a,d))

        def search(s):
            d = collections.defaultdict(lambda: inf)
            d[(-M,s)] = 0
            q = []
            heapq.heappush(q, (0, -M, s))
            v = collections.defaultdict(bool)
            while len(q):
                k, m, u = heapq.heappop(q)
                if v[(m,u)]:
                    continue
                for mm in range(m,1):
                    v[(mm,u)] = True

                for uv, ud in e[u]:
                    if ud > -m or v[(m+ud,uv)]:
                        continue
                    vd = k + ud
                    vm = m+ud
                    if uv in S:
                        vm = -M
                    if d[(vm,uv)] > vd:
                        d[(vm,uv)] = vd
                        heapq.heappush(q, (vd, vm, uv))

            return d

        d = search(A)
        r = inf
        for k in list(d.keys()):
            if k[1] == H and r > d[k]:
                r = d[k]
        if r == inf:
            rr.append('Help!')
        elif r <= M:
            rr.append(r)
        else:
            rr.append(r*2-M*2)

    return '\n'.join(map(str,rr))


print(main())

Submission status: Memory Limit Exceeded

Solution code:
import sys
import heapq

class Dijkstra(object):
  def dijkstra(self, adj, start, goal=None):
    num = len(adj)
    dist = [sys.maxint] * num
    prev = [sys.maxint] * num
    dist[start] = 0
    q = []
    heapq.heappush(q, (0, start))

    while len(q) != 0:
      prov_cost, src = heapq.heappop(q)
      if dist[src] < prov_cost: continue
      for dest in range(num):
        cost = adj[src][dest]
        if cost != sys.maxint and dist[dest] > dist[src] + cost:
          dist[dest] = dist[src] + cost
          heapq.heappush(q, (dist[dest], dest))
          prev[dest] = src
    if goal is not None:
      return self.get_path(goal, prev)
    else:
      return dist

  def get_path(self, goal, prev):
    path = [goal]
    dest = goal
    while prev[dest] != sys.maxint:
      path.append(prev[dest])
      dest = prev[dest]
    return list(reversed(path))

while True:
  N,M,L,K,A,H=map(int,raw_input().split())
  if N==0: break
  # t(n,t) : minimum cost to remain t times and reach town n
  Ls=map(int,raw_input().split())
  edge=[[sys.maxint]*(N*(M+1)) for _ in xrange(N*(M+1))]
  for l in Ls:
    for i in xrange(M):
      edge[l*(M+1)+i][l*(M+1)+i+1]=1
  for _ in xrange(K):
    s,g,c=map(int,raw_input().split())
    for i in xrange(c,M+1):
      edge[s*(M+1)+i][g*(M+1)+i-c]=c
      edge[g*(M+1)+i][s*(M+1)+i-c]=c
  cost=Dijkstra().dijkstra(edge, A*(M+1)+M)
  minCost=sys.maxint
  for i in xrange(M+1):
    minCost=min(minCost,cost[H*(M+1)+i])
  if minCost==sys.maxint: print "Help!"
  else: print minCost

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
INF = 10 ** 20

def main():
  while True:
    n, m, l, k, a, h = map(int, input().split())
    if n == 0:
      break
  
    if l == 0:
      input()
      sisetu = [a, h]
    else:
      sisetu = list(map(int, input().split()))
      sisetu += [a, h]
  
    edges = [[] for _ in range((m + 1) * n)]
    for _ in range(k):
      x, y, t = map(int, input().split())
      for i in range(t, m + 1):
        edges[i * n + x].append((t, (i - t) * n + y))
        edges[i * n + y].append((t, (i - t) * n + x))
    
    for node in sisetu:
      for i in range(m):
        edges[i * n + node].append((1, (i + 1) * n + node))
  
    que = []
    heappush(que, (0, m * n + a))
    costs = [INF] * ((m + 1) * n)
    costs[m * n + a] = 0
    
    while que:
      total, node = heappop(que)
      for dist, to in edges[node]:
        if costs[to] > total + dist:
          costs[to] = total + dist
          heappush(que, (total + dist, to))
    ans = min([costs[i * n + h] for i in range(m + 1)])
    if ans == INF:
      print("Help!")
    else:
      print(ans)

main()

Submission status: Accepted

Solution code:
import sys
import heapq

class Dijkstra(object):
  # def dijkstra(self, adj, start, goal=None):
  def dijkstra(self, num, path, start, goal=None):
    # num = len(adj)
    dist = [sys.maxint] * num
    prev = [sys.maxint] * num
    dist[start] = 0
    q = []
    heapq.heappush(q, (0, start))

    while len(q) != 0:
      prov_cost, src = heapq.heappop(q)
      if dist[src] < prov_cost: continue
      if src not in path: continue
      for dest,cost in path[src]:
        if dist[dest] > dist[src] + cost:
          dist[dest] = dist[src] + cost
          heapq.heappush(q, (dist[dest], dest))
          prev[dest] = src
      # for dest in range(num):
      #   cost = adj[src][dest]
      #   if cost != sys.maxint and dist[dest] > dist[src] + cost:
      #     dist[dest] = dist[src] + cost
      #     heapq.heappush(q, (dist[dest], dest))
      #     prev[dest] = src
    if goal is not None:
      return self.get_path(goal, prev)
    else:
      return dist

  def get_path(self, goal, prev):
    path = [goal]
    dest = goal
    while prev[dest] != sys.maxint:
      path.append(prev[dest])
      dest = prev[dest]
    return list(reversed(path))

while True:
  N,M,L,K,A,H=map(int,raw_input().split())
  if N==0: break
  # t(n,t) : minimum cost to remain t times and reach town n
  Ls=map(int,raw_input().split())
  # edge=[[sys.maxint]*(N*(M+1)) for _ in xrange(N*(M+1))]
  edge={}
  for l in Ls:
    for i in xrange(M):
      edge[l*(M+1)+i]=[(l*(M+1)+i+1,1)]
  for _ in xrange(K):
    s,g,c=map(int,raw_input().split())
    for i in xrange(c,M+1):
      if s*(M+1)+i not in edge: edge[s*(M+1)+i]=[]
      if g*(M+1)+i not in edge: edge[g*(M+1)+i]=[]
      edge[s*(M+1)+i].append((g*(M+1)+i-c,c))
      edge[g*(M+1)+i].append((s*(M+1)+i-c,c))
  cost=Dijkstra().dijkstra(N*(M+1), edge, A*(M+1)+M)
  minCost=sys.maxint
  for i in xrange(M+1):
    minCost=min(minCost,cost[H*(M+1)+i])
  if minCost==sys.maxint: print "Help!"
  else: print minCost

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
while 1:
    N, M, L, K, A, H = map(int, raw_input().split())
    if N == 0:
        break
    F = [0]*N
    for e in map(int, raw_input().split()):
        F[e] = 1
    G = [[] for i in xrange(N)]
    for i in xrange(K):
        x, y, t = map(int, raw_input().split())
        G[x].append((y, t))
        G[y].append((x, t))
    dist = [[10**18]*(M+1) for i in xrange(N)]
    dist[A][M] = 0
    que = [(0, A, M)]
    while que:
        cost, v, rest = heappop(que)
        if dist[v][rest] < cost:
            continue
        if F[v] and rest < M and cost + 1 < dist[v][rest+1]:
            dist[v][rest+1] = cost+1
            heappush(que, (cost+1, v, rest+1))
        for t, co in G[v]:
            if rest>=co and cost + co < dist[t][rest-co]:
                dist[t][rest-co] = cost + co
                heappush(que, (cost+co, t, rest-co))
    ans = min(dist[H])
    print "Help!" if ans > 10**17 else ans

Submission status: Accepted

Solution code:
from heapq import heappop, heappush


def dijkstra(links, n, m, freezables, s, t):
    queue = [(0, 0, s, m)]
    visited = [0] * n
    while queue:
        link_cost, cost, node, remain = heappop(queue)
        if node == t:
            # Congratulations!
            if link_cost <= m:
                return link_cost
            return cost - remain
        if visited[node] >= remain:
            continue
        visited[node] = remain
        for cost2, node2 in links[node]:
            if remain < cost2:
                continue
            if node2 in freezables:
                heappush(queue, (link_cost + cost2, cost + cost2 * 2 + m - remain, node2, m))
            else:
                heappush(queue, (link_cost + cost2, cost + cost2, node2, remain - cost2))
    return 'Help!'


while True:
    n, m, l, k, a, h = map(int, input().split())
    if n == 0:
        break
    freezables = set(map(int, input().split())) if l > 0 else set()
    links = [set() for _ in range(n)]
    for _ in range(k):
        x, y, t = map(int, input().split())
        links[x].add((t, y))
        links[y].add((t, x))
    print(dijkstra(links, n, m, freezables, a, h))

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353
dd = [(0,-1),(1,0),(0,1),(-1,0)]
ddn = [(0,-1),(1,-1),(1,0),(1,1),(0,1),(-1,-1),(-1,0),(-1,1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    while True:
        N,M,L,K,A,H = LI()
        if N == 0:
            break
        S = set()
        if L > 0:
            S = set(LI())
        else:
            input()
        e = collections.defaultdict(list)
        for _ in range(K):
            a,b,d = LI()
            e[a].append((b,d))
            e[b].append((a,d))

        def search(s):
            d = collections.defaultdict(lambda: inf)
            d[(-M,s)] = 0
            q = []
            heapq.heappush(q, (0, -M, s))
            v = collections.defaultdict(bool)
            while len(q):
                k, m, u = heapq.heappop(q)
                if v[(m,u)]:
                    continue
                for mm in range(m,1):
                    v[(mm,u)] = True

                for uv, ud in e[u]:
                    if ud > -m or v[(m+ud,uv)]:
                        continue
                    vd = k + ud
                    vm = m+ud
                    if uv in S:
                        vm = -M
                    if d[(vm,uv)] > vd:
                        d[(vm,uv)] = vd
                        heapq.heappush(q, (vd, vm, uv))

            return d

        d = search(A)
        r = inf
        for k in list(d.keys()):
            if k[1] == H and r > d[k]:
                r = d[k]
        if r == inf:
            rr.append('Help!')
        elif r <= M:
            rr.append(r)
        else:
            rr.append(r*2-M)

    return '\n'.join(map(str,rr))


print(main())

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop
INF = 10 ** 20

while True:
  n, m, l, k, a, h = map(int, input().split())
  if n == 0:
    break
  if l != 0:
    sisetu = list(map(int, input().split())) + [a, h]
  else:
    sisetu = [a, h]

  costs = [[INF] * n for _ in range(n)]
  for _  in range(k):
    x, y, t = map(int, input().split())
    costs[x][y] = t
    costs[y][x] = t
  for i in range(n):
    costs[i][i] = 0
  for k in range(n):
    for j in range(n):
      for i in range(n):
        costs[i][j] = min(costs[i][j], costs[i][k] + costs[k][j])

  edges = [[] for _ in range(n)]
  for i in range(n):
    for j in range(n):
      if i != j and i in sisetu and j in sisetu and costs[i][j] <= m:
        edges[i].append((costs[i][j], j))

  que = []
  heappush(que, (0, a))
  cost = [INF] * n
  cost[0] = 0
  while que:
    total, node = heappop(que)
    for dist, to in edges[node]:
      if total + dist < cost[to]:
        cost[to] = total + dist
        heappush(que, (total + dist, to))
  if cost[h] == INF:
    print("Help!")
  else:
    print(cost[h] + (cost[h] - m))

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop
INF = 10 ** 20

def main():
  while True:
    n, m, l, k, a, h = map(int, input().split())
    if n == 0:
      break
    if l != 0:
      sisetu = list(map(int, input().split())) + [a, h]
    else:
      input()
      sisetu = [a, h]
  
    costs = [[INF] * n for _ in range(n)]
    for _  in range(k):
      x, y, t = map(int, input().split())
      costs[x][y] = t
      costs[y][x] = t
    for k in range(n):
      costsk = costs[k]
      for i in range(n):
        costsi = costs[i]
        costsik = costsi[k]
        for j in range(i + 1, n):
          costsij = costsi[j]
          costsikj = costsik + costsk[j]
          if costsij > costsikj:
              costsi[j] = costsikj
              costs[j][i] = costsikj
  
    edges = [[] for _ in range(n)]
    for i in range(n):
      for j in range(i + 1, n):
        if i in sisetu and j in sisetu and costs[i][j] <= m:
          edges[i].append((costs[i][j], j))
          edges[j].append((costs[i][j], i))
  
    que = []
    heappush(que, (0, a))
    cost = [INF] * n
    cost[a] = 0
    while que:
      total, node = heappop(que)
      for dist, to in edges[node]:
        if total + dist < cost[to]:
          cost[to] = total + dist
          heappush(que, (total + dist, to))
    if cost[h] == INF:
      print("Help!")
    else:
      print(cost[h] + max(0, (cost[h] - m)))

main()

Submission status: Runtime Error

Solution code:
# AOJ2021

N = M = L = K = A = H = 0

def nexttown():
    for r in range(0, N):
        dic[r] = [t[1:3] for t in town if t[0] == r] + [ [t[0], t[2]] for t in town if t[1] == r]

def solve():
    solve2(A, M, 0)
    if mint == 100000000:
        return "Help!"
    return mint

def solve2(r, t, lv):
    global mint
    ntown = dic[r]
    for nt in ntown:
        town, time = nt
        tt = t - time #if t - time > 0 else 0
        if tt >= 0:
            if not(town in freezer):
                if dp[tt][town] == 0 or min(dp[tt][town], mint) > dp[t][r] + time:
                    dp[tt][town] = dp[t][r] + time
                    if town != H:
                        solve2(town, tt, lv + 1)
                    elif mint > dp[tt][town]:
                        mint = dp[tt][town]
            else:
                for j in range(M - tt, -1, -1):
                    if dp[tt + j][town] == 0 or min(dp[tt + j][town], mint) > dp[t][r] + j + time:
                        dp[tt + j][town] = dp[t][r] + j + time
                        if town != H:
                            solve2(town, tt + j, lv + 1)
                        elif mint > dp[tt + j][town]:
                            mint = dp[tt + j][town]
               
                
while True:
    town = []
    freezer = []
    dp = []
    dic = {}
    mint = 100000000
    line = input()
    N, M, L, K, A, H = map(int, line.split())
    if N == 0 and M == 0 and L == 0:
        break
    if L > 0:
        freezer = list(map(int, list(input().split())))
    for _ in range(0, K):
        t = list(map(int, list(input().split())))
        town.append(t)
    dp = [ [0] * N for _ in range(0, M + 1) ]  
    nexttown()
    print(solve())

Submission status: Runtime Error

Solution code:
# AOJ2021

town = []
freezer = []
dp = []
dic = {}
mint = 100000000
N = M = L = K = A = H = 0

def nexttown():
    for r in range(0, N):
        dic[r] = [t[1:3] for t in town if t[0] == r] + [ [t[0], t[2]] for t in town if t[1] == r]

def solve():
    solve2(A, M, 0)
    if mint == 100000000:
        return "Help!"
    return mint

def solve2(r, t, lv):
    global mint
    ntown = dic[r]
    for nt in ntown:
        town, time = nt
        tt = t - time
        if tt >= 0:
            if not(town in freezer):
                if dp[tt][town] == 0 or min(dp[tt][town], mint) > dp[t][r] + time:
                    dp[tt][town] = dp[t][r] + time
                    if town != H:
                        solve2(town, tt, lv + 1)
                    elif mint > dp[tt][town]:
                        mint = dp[tt][town]
            else:
                for j in range(M - tt, -1, -1):
                    if dp[tt + j][town] == 0 or min(dp[tt + j][town], mint) > dp[t][r] + j + time:
                        dp[tt + j][town] = dp[t][r] + j + time
                        if town != H:
                            solve2(town, tt + j, lv + 1)
                        elif mint > dp[tt + j][town]:
                            mint = dp[tt + j][town]
               
                
while True:
    town = []
    freezer = []
    dp = []
    dic = {}
    mint = 100000000
    line = input()
    N, M, L, K, A, H = map(int, line.split())
    if N == 0 and M == 0 and L == 0:
        break
    if L > 0:
        freezer = list(map(int, list(input().split())))
    for _ in range(0, K):
        t = list(map(int, list(input().split())))
        town.append(t)
    dp = [ [0] * N for _ in range(0, M + 1) ]  
    nexttown()
    print(solve())

Submission status: Runtime Error

Solution code:
# AOJ2021

town = []
freezer = []
dp = []
dic = {}
mint = 100000000

def nexttown():
    for r in range(0, N):
        dic[r] = [t[1:3] for t in town if t[0] == r] + [ [t[0], t[2]] for t in town if t[1] == r]

def solve():
    solve2(A, M, 0)
    if mint == 100000000:
        return "Help!"
    return mint

def solve2(r, t, lv):
    global mint
    ntown = dic[r]
    for nt in ntown:
        town, time = nt
        tt = t - time
        if tt >= 0:
            if not(town in freezer):
                if dp[tt][town] == 0 or min(dp[tt][town], mint) > dp[t][r] + time:
                    dp[tt][town] = dp[t][r] + time
                    if town != H:
                        solve2(town, tt, lv + 1)
                    elif mint > dp[tt][town]:
                        mint = dp[tt][town]
            else:
                for j in range(M - tt, -1, -1):
                    if dp[tt + j][town] == 0 or min(dp[tt + j][town], mint) > dp[t][r] + j + time:
                        dp[tt + j][town] = dp[t][r] + j + time
                        if town != H:
                            solve2(town, tt + j, lv + 1)
                        elif mint > dp[tt + j][town]:
                            mint = dp[tt + j][town]
               
                
while True:
    town = []
    freezer = []
    dp = []
    dic = {}
    mint = 100000000
    line = input()
    N, M, L, K, A, H = map(int, line.split())
    if N == 0 and M == 0 and L == 0:
        break
    if L > 0:
        freezer = list(map(int, list(input().split())))
    for _ in range(0, K):
        t = list(map(int, list(input().split())))
        town.append(t)
    dp = [ [0] * N for _ in range(0, M + 1) ]  
    nexttown()
    print(solve())

Submission status: Runtime Error

Solution code:
# AOJ2021

town = []
freezer = []
dp = []
dic = {}
mint = 100000000

def nexttown():
    for r in range(0, N):
        dic[r] = [t[1:3] for t in town if t[0] == r] + [ [t[0], t[2]] for t in town if t[1] == r]

def solve():
    solve2(A, M, 0)
#    if mint == 100000000:
#        return "Help!"
    return mint

def solve2(r, t, lv):
    global mint
    ntown = dic[r]
    for nt in ntown:
        town, time = nt
        tt = t - time
        if tt >= 0:
            if not(town in freezer):
                if dp[tt][town] == 0 or min(dp[tt][town], mint) > dp[t][r] + time:
                    dp[tt][town] = dp[t][r] + time
                    if town != H:
                        solve2(town, tt, lv + 1)
                    elif mint > dp[tt][town]:
                        mint = dp[tt][town]
            else:
                for j in range(M - tt, -1, -1):
                    if dp[tt + j][town] == 0 or min(dp[tt + j][town], mint) > dp[t][r] + j + time:
                        dp[tt + j][town] = dp[t][r] + j + time
                        if town != H:
                            solve2(town, tt + j, lv + 1)
                        elif mint > dp[tt + j][town]:
                            mint = dp[tt + j][town]
               
                
while True:
    town = []
    freezer = []
    dp = []
    dic = {}
    mint = 100000000
    line = input()
    N, M, L, K, A, H = map(int, line.split())
    if N == 0 and M == 0 and L == 0:
        break
    if L > 0:
        freezer = list(map(int, list(input().split())))
    for _ in range(0, K):
        t = list(map(int, list(input().split())))
        town.append(t)
    dp = [ [0] * N for _ in range(0, M + 1) ]  
    nexttown()
    print(solve())

Submission status: Runtime Error

Solution code:
# AOJ2021

town = []
freezer = []
dp = []
dic = {}
mint = 100000000

def nexttown():
    for r in range(0, N):
        dic[r] = [t[1:3] for t in town if t[0] == r] + [ [t[0], t[2]] for t in town if t[1] == r]

def solve():
    solve2(A, M, 0)
    if mint == 100000000:
        return "Help!"
    return mint

def solve2(r, t, lv):
    global mint
    ntown = dic[r]
    for nt in ntown:
        town, time = nt
        tt = t - time
        if tt >= 0:
            if not(town in freezer):
                if dp[tt][town] == 0 or min(dp[tt][town], mint) > dp[t][r] + time:
                    dp[tt][town] = dp[t][r] + time
                    if town != H:
                        solve2(town, tt, lv + 1)
                    elif mint > dp[tt][town]:
                        mint = dp[tt][town]
            else:
                for j in range(M - tt, -1, -1):
                    if dp[tt + j][town] == 0 or min(dp[tt + j][town], mint) > dp[t][r] + j + time:
                        dp[tt + j][town] = dp[t][r] + j + time
                        if town != H:
                            solve2(town, tt + j, lv + 1)
                        elif mint > dp[tt + j][town]:
                            mint = dp[tt + j][town]

while True:
    town = []
    freezer = []
    dp = []
    dic = {}
    mint = 100000000
    line = input()
    N, M, L, K, A, H = map(int, line.split())
    if N == 0 and M == 0 and L == 0:
        break
    if L > 0:
        freezer = list(map(int, list(input().split())))
    for _ in range(0, K):
        t = list(map(int, list(input().split())))
        town.append(t)
    dp = [ [0] * N for _ in range(0, M + 1) ]
    nexttown()
    print(solve())

Submission status: Runtime Error

Solution code:
def nexttown():
    for r in range(0, N):
        dic[r] = [t[1:3] for t in town if t[0] == r] + [ [t[0], t[2]] for t in town if t[1] == r]

def solve():
    solve2(A, M, 0)
    if mint == 100000000:
        return "Help!"
    return mint

def solve2(r, t, lv):
    global mint
    ntown = dic[r]
    for nt in ntown:
        town, time = nt
        tt = t - time #if t - time > 0 else 0
        if tt >= 0:
            if not(town in freezer):
                if dp[tt][town] == 0 or min(dp[tt][town], mint) > dp[t][r] + time:
                    dp[tt][town] = dp[t][r] + time
                    if town != H:
                        solve2(town, tt, lv + 1)
                    elif mint > dp[tt][town]:
                        mint = dp[tt][town]
            else:
                for j in range(M - tt, -1, -1):
                    if dp[tt + j][town] == 0 or min(dp[tt + j][town], mint) > dp[t][r] + j + time:
                        dp[tt + j][town] = dp[t][r] + j + time
                        if town != H:
                            solve2(town, tt + j, lv + 1)
                        elif mint > dp[tt + j][town]:
                            mint = dp[tt + j][town]
               

while True:
    town = []
    freezer = []
    dp = []
    dic = {}
    mint = 100000000
    line = input()
    N, M, L, K, A, H = map(int, line.split())
    if N == 0 and M == 0 and L == 0:
        break
    if L > 0:
        freezer = list(map(int, list(input().split())))
    for _ in range(0, K):
        t = list(map(int, list(input().split())))
        town.append(t)
    dp = [ [0] * N for _ in range(0, M + 1) ]  
    nexttown()
    print(solve())

Submission status: Runtime Error

Solution code:
town = []
freezer = []
dp = []
dic = {}
mint = 100000000
N = M = L = K = A = H = 0


def nexttown():
    for r in range(0, N):
        dic[r] = [t[1:3] for t in town if t[0] == r] + [ [t[0], t[2]] for t in town if t[1] == r]

def solve():
    solve2(A, M, 0)
    if mint == 100000000:
        return "Help!"
    return mint

def solve2(r, t, lv):
    global mint
    ntown = dic[r]
    for nt in ntown:
        town, time = nt
        tt = t - time #if t - time > 0 else 0
        if tt >= 0:
            if not(town in freezer):
                if dp[tt][town] == 0 or min(dp[tt][town], mint) > dp[t][r] + time:
                    dp[tt][town] = dp[t][r] + time
                    if town != H:
                        solve2(town, tt, lv + 1)
                    elif mint > dp[tt][town]:
                        mint = dp[tt][town]
            else:
                for j in range(M - tt, -1, -1):
                    if dp[tt + j][town] == 0 or min(dp[tt + j][town], mint) > dp[t][r] + j + time:
                        dp[tt + j][town] = dp[t][r] + j + time
                        if town != H:
                            solve2(town, tt + j, lv + 1)
                        elif mint > dp[tt + j][town]:
                            mint = dp[tt + j][town]
               

while True:
    town = []
    freezer = []
    dp = []
    dic = {}
    mint = 100000000
    line = input()
    N, M, L, K, A, H = map(int, line.split())
    if N == 0 and M == 0 and L == 0:
        break
    if L > 0:
        freezer = list(map(int, list(input().split())))
    for _ in range(0, K):
        t = list(map(int, list(input().split())))
        town.append(t)
    dp = [ [0] * N for _ in range(0, M + 1) ]  
    nexttown()
    print(solve())