Problem:


自転車でダイエット

  A さんは甘いものが大好きですが、最近は奥さんからダイエットするように言われています。ある日、A さんが自宅から市役所に出かけるとき、奥さんは自転車で行くことを勧めました。そこでA さんはしぶしぶ自転車に乗って出かけましたが、甘い物の好きな A さんは、途中にあるケーキ屋さんに立ち寄りケーキの食べ歩きをしようと思いつきました。

  自転車をこげば走行距離に応じてカロリーが消費されますが、ケーキを食べればその分カロリーが摂取されます。正味の消費カロリーは、自転車をこいで消費したカロリーからケーキを食べて摂取したカロリーを引いた値になります。したがって、正味の消費カロリーが 0 より小さくなることもあります。

  ケーキ屋さんでケーキを買ったら、 Aさんはその場でケーキを全部食べてしまいます。 Aさんがすべてのケーキ屋さんに立ち寄るとは限りませんが、ケーキ屋さんが存在する地点を通るときには、必ず立ち寄ってケーキを 1 つ買って食べるものとします。ただし、同じケーキ屋さんの前を何度も通るのはさすがに気がひけるので、各ケーキ屋さんに訪れられるのは 1 回だけとします。また、目的地の市役所をいったん通り過ぎてからケーキ屋さんに立ち寄り、その後で市役所に戻って用を済ませてもよいものとし、ケーキ屋さん以外は何度訪れても良いものとします。

  A さんの自宅から市役所までの地図情報と、その途中にあるケーキ屋さんで食べられるケーキのカロリーの一覧、単位距離の走行による消費カロリーを入力とし、自宅を出発してから市役所に入るまでの正味の消費カロリーの最小値を出力するプログラムを作成してください。

  地図には、A さんの自宅と市役所、ケーキ屋さんとランドマーク(目印)になる建物が書かれています。地図を表す入力データは、A さんの自宅、市役所、ケーキ屋さんとランドマークの各地点の間をつなぐ道があるとき、2 つの地点を表す記号とその間の距離からなる行を含みます。たとえば、5 番目のケーキ屋さんと 3 番目のランドマークの間の距離が 10 なら、入力データは以下のような行を含みます。

C5 L3 10

  このようにケーキ屋さんには C、ランドマークには L を番号の前につけて表します。また、A さんの自宅は H、市役所は D で表します。入力データに 2 つの地点とその間の距離が与えられているなら、2 地点の間をどちら向きにも進めます。たとえば、上の例ではケーキ屋さんからランドマークへも、その逆向きへも進むことができます。また、自宅から市役所までは必ずたどり着けるものとします。それ以外に与えられる入力データは、ケーキ屋さんの数 m、ランドマークの数 n、単位距離あたりの消費カロリー k、 1 番目のケーキ屋さんから m 番目のケーキ屋さんまでのそれぞれで買えるケーキのカロリーを表す m 個のデータ、距離のデータの総数 d です。

Input

  複数のデータセットの並びが入力として与えられます。入力の終わりは四つの 0 の行で示されます。
  各データセットは以下の形式で与えられます。

m n k d
c1 c2 ... cm
s1 t1 e1
s2 t2 e2
:
sd td ed

1 行目にケーキ屋さんの数 m (1 ≤ m ≤ 6)、 ランドマークの数 n (1 ≤ n ≤ 100) 、単位距離あたりの消費カロリー k (1 ≤ k ≤ 5)、距離のデータの総数 d (5 ≤ d ≤ 256) が与えられます。

2 行目に各ケーキ屋で買うケーキのカロリー ci (1 ≤ ci ≤ 100) が与えられます。

続く d 行に i 番目の 2 つの地点間の距離データ si, ti, ei (1 ≤ ei ≤ 20)  が与えられます。

データセットの数は 100 を超えません。

Output

入力データセットごとに、全体の消費カロリーの最小値を１行に出力します。

Sample Input

1 1 2 5
35
H L1 5
C1 D 6
C1 H 12
L1 D 10
C1 L1 20
2 1 4 6
100 70
H L1 5
C1 L1 12
C1 D 11
C2 L1 7
C2 D 15
L1 D 8
0 0 0 0

Output for the Sample Input

1
-2



Sample input:
1 1 2 5
35
H L1 5
C1 D 6
C1 H 12
L1 D 10
C1 L1 20
2 1 4 6
100 70
H L1 5
C1 L1 12
C1 D 11
C2 L1 7
C2 D 15
L1 D 8
0 0 0 0


Sample output:
1
-2

Submission status: Wrong Answer

Solution code:
def getid(node, m, n):
    if node == 'H':
        return 0
    elif node == 'D':
        return m + n + 1
    elif node[0] == 'C':
        return int(node[1:])
    else:
        return m + int(node[1:])
import heapq

def dijkstra(graph, size, start=0):
    distance = [float('inf')] * size
    distance[start] = 0
    que = []
    heapq.heappush(que, (0, start))
    while len(que):
        _, u = heapq.heappop(que)
        for length, vi in graph[u]:
            if distance[vi] > distance[u] + length:
                distance[vi] = distance[u] + length
                heapq.heappush(que, (distance[vi], vi))
    return distance
import sys
f = sys.stdin


from collections import defaultdict
from itertools import permutations
from itertools import chain

while True:
    m,n,k,d = map(int, f.readline().split())
    if m == n == k == d == 0:
        break
    cake = [0] + list(map(int, f.readline().split()))
    graph = defaultdict(list)
    for a, b, dist in [f.readline().split() for _ in range(d)]:
        a, b, dist = getid(a,m,n), getid(b,m,n), int(dist) * k
        graph[a].append((dist,b))
        graph[b].append((dist,a))
        
    compressed_graph = [dijkstra(graph, m + n + 2, i) for i in range(m + 1)]

    calorie = []
    for combination in chain(*[permutations(range(1,m + 1), i) for i in range(m + 1)]):
        combination = (0,) + combination + (m + n + 1,)
        temp = -sum(cake[i] for i in combination[:-1])
        for s, e in zip(combination,combination[1:]):
            temp += compressed_graph[s][e]
        calorie.append(temp)
    print(min(calorie))

Submission status: Wrong Answer

Solution code:
from itertools import combinations
from heapq import heappop, heappush
import sys
sys.setrecursionlimit(1000000)
INF = 10 ** 20

def convert(s, m, n):
  if s == "H":
    return 0
  if s == "D":
    return 1
  if s[0] == "C":
    return int(s[1]) + 1
  if s[0] == "L":
    return int(s[1]) + m + 1

def get_cost(start, m, n, edges):
  cost = [INF] * (m + n + 2)
  cost[start] = 0
  que = []
  heappush(que, (0, start))
  while que:
    total, node = heappop(que)
    for dist, to in edges[node]:
      if cost[to] > total + dist:
        cost[to] = total + dist
        if not (2 <= to <= m + 1):
          heappush(que, (total + dist, to))
  return cost


def shortest_path(start, goal, rest, cakes_dist, dic):
  if not rest:
    return cakes_dist[start][goal]
  if (start, rest) in dic:
    return dic[(now, rest)]
  
  ret = INF
  for to in rest:
    ret = min(ret, shortest_path(to, goal, tuple((i for i in rest if i != to)), cakes_dist, dic) + cakes_dist[start][to])
  dic[(start, rest)] = ret
  return ret

while True:
  m, n, k, d = map(int, input().split())
  if m == 0:
    break
  clst = list(map(int, input().split()))
  """
  Home ... 0
  D ... 1
  Cake ... 2, 3, ... m + 1
  Land ... m + 2, m + 3, ... m + n + 1
  """
  edges = [[] for _ in range(m + n + 2)]
  for _ in range(d):
    s, t, e = input().split()
    e = int(e)
    s = convert(s, m, n)
    t = convert(t, m, n)
    edges[s].append((e, t))
    edges[t].append((e, s))

Submission status: Wrong Answer

Solution code:
from itertools import combinations
from heapq import heappop, heappush
import sys
sys.setrecursionlimit(1000000)
INF = 10 ** 20

def convert(s, m, n):
  if s == "H":
    return 0
  if s == "D":
    return 1
  if s[0] == "C":
    return int(s[1]) + 1
  if s[0] == "L":
    return int(s[1]) + m + 1

def get_cost(start, m, n, edges):
  cost = [INF] * (m + n + 2)
  cost[start] = 0
  que = []
  heappush(que, (0, start))
  while que:
    total, node = heappop(que)
    for dist, to in edges[node]:
      if cost[to] > total + dist:
        cost[to] = total + dist
        if not (2 <= to <= m + 1):
          heappush(que, (total + dist, to))
  return cost


def shortest_path(start, goal, rest, cakes_dist, dic):
  if not rest:
    return cakes_dist[start][goal]
  if (start, rest) in dic:
    return dic[(now, rest)]
  
  ret = INF
  for to in rest:
    ret = min(ret, shortest_path(to, goal, tuple((i for i in rest if i != to)), cakes_dist, dic) + cakes_dist[start][to])
  dic[(start, rest)] = ret
  return ret

while True:
  m, n, k, d = map(int, input().split())
  if m == 0:
    break
  clst = list(map(int, input().split()))
  """
  Home ... 0
  D ... 1
  Cake ... 2, 3, ... m + 1
  Land ... m + 2, m + 3, ... m + n + 1
  """
  edges = [[] for _ in range(m + n + 2)]
  for _ in range(d):
    s, t, e = input().split()
    e = int(e)
    s = convert(s, m, n)
    t = convert(t, m, n)
    edges[s].append((e, t))
    edges[t].append((e, s))
  
  cakes_dist = [[INF] * (m + 2) for _ in range(m + 2)]
  for start in range(m + 2):
    cost = get_cost(start, m, n, edges)
    for to in range(m + 2):
      if to != start:
        cakes_dist[start][to] = cost[to]

Submission status: Wrong Answer

Solution code:
from itertools import combinations
from heapq import heappop, heappush
import sys
sys.setrecursionlimit(1000000)
INF = 10 ** 20

def convert(s, m, n):
  if s == "H":
    return 0
  if s == "D":
    return 1
  if s[0] == "C":
    return int(s[1]) + 1
  if s[0] == "L":
    return int(s[1]) + m + 1

def get_cost(start, m, n, edges):
  cost = [INF] * (m + n + 2)
  cost[start] = 0
  que = []
  heappush(que, (0, start))
  while que:
    total, node = heappop(que)
    for dist, to in edges[node]:
      if cost[to] > total + dist:
        cost[to] = total + dist
        if not (2 <= to <= m + 1):
          heappush(que, (total + dist, to))
  return cost


def shortest_path(start, goal, rest, cakes_dist, dic):
  if not rest:
    return cakes_dist[start][goal]
  if (start, rest) in dic:
    return dic[(now, rest)]
  
  ret = INF
  for to in rest:
    ret = min(ret, shortest_path(to, goal, tuple((i for i in rest if i != to)), cakes_dist, dic) + cakes_dist[start][to])
  dic[(start, rest)] = ret
  return ret

while True:
  m, n, k, d = map(int, input().split())
  if m == 0:
    break
  clst = list(map(int, input().split()))
  """
  Home ... 0
  D ... 1
  Cake ... 2, 3, ... m + 1
  Land ... m + 2, m + 3, ... m + n + 1
  """
  edges = [[] for _ in range(m + n + 2)]
  for _ in range(d):
    s, t, e = input().split()
    e = int(e)
    s = convert(s, m, n)
    t = convert(t, m, n)
    edges[s].append((e, t))
    edges[t].append((e, s))
  
  cakes_dist = [[INF] * (m + 2) for _ in range(m + 2)]
  for start in range(m + 2):
    cost = get_cost(start, m, n, edges)
    for to in range(m + 2):
      if to != start:
        cakes_dist[start][to] = cost[to]
  dic = {}
  """
  now ... 現在いる点
  rest ... 残りのめぐる点
  dic[(now, rest)] ... 現在いる点、残りの点をまわる時の最小距離
  dic[(now, rest)] = min(cakes_dist[now][to] + dic[(to, rest - to)] for to in rest)
  """
  ans = INF
  cakes = [i for i in range(2, m + 2)]
  for num in range(m + 1):
    for rest in combinations(cakes, num):
      cal = sum([clst[i - 2] for i in rest])
      #ans = min(ans, shortest_path(0, 1, rest, cakes_dist, dic) * k - cal)
  print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import combinations
from heapq import heappop, heappush
import sys
sys.setrecursionlimit(1000000)
INF = 10 ** 20

def convert(s, m, n):
  if s == "H":
    return 0
  if s == "D":
    return 1
  if s[0] == "C":
    return int(s[1]) + 1
  if s[0] == "L":
    return int(s[1]) + m + 1

def get_cost(start, m, n, edges):
  cost = [INF] * (m + n + 2)
  cost[start] = 0
  que = []
  heappush(que, (0, start))
  while que:
    total, node = heappop(que)
    for dist, to in edges[node]:
      if cost[to] > total + dist:
        cost[to] = total + dist
        if not (2 <= to <= m + 1):
          heappush(que, (total + dist, to))
  return cost


def shortest_path(start, goal, rest, cakes_dist, dic):
  if not rest:
    return cakes_dist[start][goal]
  if (start, rest) in dic:
    return dic[(start, rest)]
  
  ret = INF
  for to in rest:
    ret = min(ret, shortest_path(to, goal, tuple((i for i in rest if i != to)), cakes_dist, dic) + cakes_dist[start][to])
  dic[(start, rest)] = ret
  return ret

while True:
  m, n, k, d = map(int, input().split())
  if m == 0:
    break
  clst = list(map(int, input().split()))
  """
  Home ... 0
  D ... 1
  Cake ... 2, 3, ... m + 1
  Land ... m + 2, m + 3, ... m + n + 1
  """
  edges = [[] for _ in range(m + n + 2)]
  for _ in range(d):
    s, t, e = input().split()
    e = int(e)
    s = convert(s, m, n)
    t = convert(t, m, n)
    edges[s].append((e, t))
    edges[t].append((e, s))
  
  cakes_dist = [[INF] * (m + 2) for _ in range(m + 2)]
  for start in range(m + 2):
    cost = get_cost(start, m, n, edges)
    for to in range(m + 2):
      if to != start:
        cakes_dist[start][to] = cost[to]
  dic = {}
  """
  now ... 現在いる点
  rest ... 残りのめぐる点
  dic[(now, rest)] ... 現在いる点、残りの点をまわる時の最小距離
  dic[(now, rest)] = min(cakes_dist[now][to] + dic[(to, rest - to)] for to in rest)
  """
  ans = INF
  cakes = [i for i in range(2, m + 2)]
  for num in range(m + 1):
    for rest in combinations(cakes, num):
      cal = sum([clst[i - 2] for i in rest])
      ans = min(ans, shortest_path(0, 1, rest, cakes_dist, dic) * k - cal)
  print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import combinations
from heapq import heappop, heappush
import sys
sys.setrecursionlimit(1000000)
INF = 10 ** 20

def convert(s, m, n):
  if s == "H":
    return 0
  if s == "D":
    return 1
  if s[0] == "C":
    return int(s[1]) + 1
  if s[0] == "L":
    return int(s[1]) + m + 1

def get_cost(start, m, n, edges):
  cost = [INF] * (m + n + 2)
  cost[start] = 0
  que = []
  heappush(que, (0, start))
  while que:
    total, node = heappop(que)
    for dist, to in edges[node]:
      if cost[to] > total + dist:
        cost[to] = total + dist
        if not (2 <= to <= m + 1):
          heappush(que, (total + dist, to))
  return cost


def shortest_path(start, goal, rest, cakes_dist, dic):
  if not rest:
    return cakes_dist[start][goal]
  if (start, rest) in dic:
    return dic[(start, rest)]
  
  ret = INF
  for to in rest:
    ret = min(ret, shortest_path(to, goal, tuple((i for i in rest if i != to)), cakes_dist, dic) + cakes_dist[start][to])
  dic[(start, rest)] = ret
  return ret

while True:
  m, n, k, d = map(int, input().split())
  if m == 0:
    break
  clst = list(map(int, input().split()))
  """
  Home ... 0
  D ... 1
  Cake ... 2, 3, ... m + 1
  Land ... m + 2, m + 3, ... m + n + 1
  """
  edges = [[] for _ in range(m + n + 2)]
  for _ in range(d):
    s, t, e = input().split()
    e = int(e)
    s = convert(s, m, n)
    t = convert(t, m, n)
    edges[s].append((e, t))
    edges[t].append((e, s))
  
  cakes_dist = [[INF] * (m + 2) for _ in range(m + 2)]
  for start in range(m + 2):
    cost = get_cost(start, m, n, edges)
    for to in range(m + 2):
      if to != start:
        cakes_dist[start][to] = cost[to]
  """
  now ... 現在いる点
  rest ... 残りのめぐる点
  dic[(now, rest)] ... 現在いる点、残りの点をまわる時の最小距離
  dic[(now, rest)] = min(cakes_dist[now][to] + dic[(to, rest - to)] for to in rest)
  """
  ans = INF
  cakes = [i for i in range(2, m + 2)]
  for num in range(m + 1):
    for rest in combinations(cakes, num):
      dic = {}
      cal = sum([clst[i - 2] for i in rest])
      ans = min(ans, shortest_path(0, 1, rest, cakes_dist, dic) * k - cal)
  print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import combinations
from heapq import heappop, heappush
import sys
sys.setrecursionlimit(1000000)
INF = 10 ** 20

def convert(s, m, n):
  if s == "H":
    return 0
  if s == "D":
    return 1
  if s[0] == "C":
    return int(s[1]) + 1
  if s[0] == "L":
    return int(s[1]) + m + 1

def get_cost(start, m, n, edges):
  cost = [INF] * (m + n + 2)
  cost[start] = 0
  que = []
  heappush(que, (0, start))
  while que:
    total, node = heappop(que)
    for dist, to in edges[node]:
      if cost[to] > total + dist:
        cost[to] = total + dist
        #if not (2 <= to <= m + 1):
        heappush(que, (total + dist, to))
  return cost


def shortest_path(start, goal, rest, cakes_dist, dic):
  if not rest:
    return cakes_dist[start][goal]
  if (start, rest) in dic:
    return dic[(start, rest)]
  
  ret = INF
  for to in rest:
    ret = min(ret, shortest_path(to, goal, tuple((i for i in rest if i != to)), cakes_dist, dic) + cakes_dist[start][to])
  dic[(start, rest)] = ret
  return ret

while True:
  m, n, k, d = map(int, input().split())
  if m == 0:
    break
  clst = list(map(int, input().split()))
  """
  Home ... 0
  D ... 1
  Cake ... 2, 3, ... m + 1
  Land ... m + 2, m + 3, ... m + n + 1
  """
  edges = [[] for _ in range(m + n + 2)]
  for _ in range(d):
    s, t, e = input().split()
    e = int(e)
    s = convert(s, m, n)
    t = convert(t, m, n)
    edges[s].append((e, t))
    edges[t].append((e, s))
  
  cakes_dist = [[INF] * (m + 2) for _ in range(m + 2)]
  for start in range(m + 2):
    cost = get_cost(start, m, n, edges)
    for to in range(m + 2):
      if to != start:
        cakes_dist[start][to] = cost[to]
  
  """
  now ... 現在いる点
  rest ... 残りのめぐる点
  dic[(now, rest)] ... 現在いる点、残りの点をまわる時の最小距離
  dic[(now, rest)] = min(cakes_dist[now][to] + dic[(to, rest - to)] for to in rest)
  """
  dic = {}
  ans = INF
  cakes = [i for i in range(2, m + 2)]
  for num in range(m + 1):
    for rest in combinations(cakes, num):
      cal = sum([clst[i - 2] for i in rest])
      ans = min(ans, shortest_path(0, 1, rest, cakes_dist, dic) * k - cal)
  print(ans)

Submission status: Accepted

Solution code:
# ref: http://lethe2211.hatenablog.com/entry/2014/12/30/011030
# ref: http://d.hatena.ne.jp/simezi_tan/20101019/1287462266
from heapq import heappop,heappush

if __name__ == '__main__':
    def id(s):
        # edges = [C1 C2 C3...Cm L1 L2 L3...Ln H D]
        # len(edges) = m+n+1+1
        if s[0]=="H": return ne-2
        if s[0]=="D": return ne-1
        num = int(s[1:])
        if s[0]=="C": return num-1
        return num-1+m
    while(True):
        m,n,k,d = map(int, input().split())
        if not m: break
        ne = m+n+2
        cs = list(map(int, input().split()))
        edges = [[] for _ in range(ne) ]
        for i in range(d):
            s1,s2,di = input().split()
            t1,t2,ca = id(s1),id(s2),int(di)*k
            edges[t1].append([t2,ca])
            edges[t2].append([t1,ca])
        que = []
        cost = [float('inf')]*(ne<<m)
        cost[(ne-2)<<m] = 0
        ans = float('inf')
        heappush(que,[0,(ne-2)<<m])
        while(que):
            cc,state = heappop(que)
            vis_cak = state&(2**m-1)
            cur_pos = state>>m
            if cur_pos == ne-1: ans = min(ans,cc)
            if cost[state]>cc: continue
            for ss,dd in edges[cur_pos]:
                nxt_cost = cc+dd
                nxt_pos = ss
                nxt_bit = vis_cak
                # calc cakeshop (visit one time only)
                if 0<=nxt_pos and nxt_pos<m:
                    if 1<<nxt_pos & vis_cak: continue
                    nxt_cost -= cs[nxt_pos]
                    nxt_bit ^= 1 << nxt_pos
                # combine next_position and visited_cakeshop
                new_state = (nxt_pos<<m) + nxt_bit
                if cost[new_state] > nxt_cost:
                    heappush(que,[nxt_cost,new_state])
                    cost[new_state] = nxt_cost
        print(ans)

Submission status: Accepted

Solution code:
def getid(node, m, n):
    if node == 'H':
        return 0
    elif node == 'D':
        return m + n + 1
    elif node[0] == 'C':
        return int(node[1:])
    else:
        return m + int(node[1:])
import heapq

#??±???????±?????????±???????????????????????????
def ex_dijkstra(graph, m, size, start=0):
    distance = [float('inf')] * size
    distance[start] = 0
    que = []
    heapq.heappush(que, (0, start))
    while len(que):
        _, u = heapq.heappop(que)
        for length, vi in graph[u]:
            if distance[vi] > distance[u] + length:
                distance[vi] = distance[u] + length
                if 1 <= vi <= m:
                    continue
                heapq.heappush(que, (distance[vi], vi))
    return distance
import sys
f = sys.stdin

from collections import defaultdict
from itertools import permutations
from itertools import chain

while True:
    m,n,k,d = map(int, f.readline().split())
    if m == 0:
        break
    cake = [0] + list(map(int, f.readline().split()))
    graph = defaultdict(list)
    for a, b, dist in [f.readline().split() for _ in range(d)]:
        a, b, dist = getid(a,m,n), getid(b,m,n), int(dist) * k
        graph[a].append((dist,b))
        graph[b].append((dist,a))
    compressed_graph = [ex_dijkstra(graph, m, m + n + 2, i) for i in range(m + 1)]

    calorie = []
    for combination in chain(*[permutations(range(1,m + 1), i) for i in range(m + 1)]):
        combination = (0,) + combination + (m + n + 1,)
        temp = -sum(cake[i] for i in combination[:-1])
        for s, e in zip(combination,combination[1:]):
            temp += compressed_graph[s][e]
        calorie.append(temp)
    print(min(calorie))

Submission status: Accepted

Solution code:
import Queue
INF = 1 << 29
class Edge:
    def __init__(self, _v, _cost):
        self.v = _v
        self.cost = _cost
def parse(s, m, n):
    if(s[0]=="C"): return int(s.translate(None, "C")) - 1
    elif(s[0]=="L"): return int(s.translate(None, "L")) - 1 + m
    elif(s[0]=="H"): return m + n 
    else: return m + n + 1
while True:
    m, n, k, d = map(int, raw_input().split())
    if m==0 and n==0 and k==0 and d==0: break
    cake = map(int, raw_input().split())
    G = [[] for i in range((m + n + 2))]
    for i in range(d):
        dist = raw_input().split()
        u = parse(dist[0], m, n)
        v = parse(dist[1], m ,n)
        G[v].append(Edge(u, int(dist[2])))
        G[u].append(Edge(v, int(dist[2])))
    D = [[0  for col in range(1<<6)]  for row in range(108)]
    for i in range(m + n + 2):
        for j in range(1 << m):
            D[i][j] = INF
    D[m + n][0] = 0

    ans = INF
    que = Queue.PriorityQueue()
    que.put([0, [m + n, 0]])
    while not que.empty():
        item = que.get()
        d_now = item[0]
        u = item[1][0]
        s = item[1][1]
        if D[u][s] < d_now: continue
        if u == m + n + 1: ans = min(ans, d_now)
        for i in range(len(G[u])):
            v = G[u][i].v
            if v < m:
                if s & 1 << v != 0: continue
                s2 = s | 1 << v
                d2 = d_now + k * G[u][i].cost - cake[v]
            else:
                s2 = s
                d2 = d_now + k * G[u][i].cost
            if d2 < D[v][s2]:
                D[v][s2] = d2
                que.put([d2, [v, s2]])
    print ans

Submission status: Accepted

Solution code:
from itertools import combinations
from heapq import heappop, heappush
import sys
sys.setrecursionlimit(1000000)
INF = 10 ** 20

def convert(s, m, n):
  if s == "H":
    return 0
  if s == "D":
    return 1
  if s[0] == "C":
    return int(s[1:]) + 1
  if s[0] == "L":
    return int(s[1:]) + m + 1

def get_cost(start, m, n, edges):
  cost = [INF] * (m + n + 2)
  cost[start] = 0
  que = []
  heappush(que, (0, start))
  while que:
    total, node = heappop(que)
    for dist, to in edges[node]:
      if cost[to] > total + dist:
        cost[to] = total + dist
        if not (2 <= to <= m + 1):
          heappush(que, (total + dist, to))
  return cost


def shortest_path(start, goal, rest, cakes_dist, dic):
  if not rest:
    return cakes_dist[start][goal]
  if (start, rest) in dic:
    return dic[(start, rest)]
  
  ret = INF
  for to in rest:
    ret = min(ret, shortest_path(to, goal, tuple((i for i in rest if i != to)), cakes_dist, dic) + cakes_dist[start][to])
  dic[(start, rest)] = ret
  return ret

while True:
  m, n, k, d = map(int, input().split())
  if m == 0:
    break
  clst = list(map(int, input().split()))
  """
  Home ... 0
  D ... 1
  Cake ... 2, 3, ... m + 1
  Land ... m + 2, m + 3, ... m + n + 1
  """
  edges = [[] for _ in range(m + n + 2)]
  for _ in range(d):
    s, t, e = input().split()
    e = int(e)
    s = convert(s, m, n)
    t = convert(t, m, n)
    edges[s].append((e, t))
    edges[t].append((e, s))
  
  cakes_dist = [[INF] * (m + 2) for _ in range(m + 2)]
  for start in range(m + 2):
    cost = get_cost(start, m, n, edges)
    for to in range(m + 2):
      if to != start:
        cakes_dist[start][to] = cost[to]
  
  """
  now ... 現在いる点
  rest ... 残りのめぐる点
  dic[(now, rest)] ... 現在いる点、残りの点をまわる時の最小距離
  dic[(now, rest)] = min(cakes_dist[now][to] + dic[(to, rest - to)] for to in rest)
  """
  dic = {}
  ans = INF
  cakes = [i for i in range(2, m + 2)]
  for num in range(m + 1):
    for rest in combinations(cakes, num):
      cal = sum([clst[i - 2] for i in rest])
      ans = min(ans, shortest_path(0, 1, rest, cakes_dist, dic) * k - cal)
  print(ans)

Submission status: Accepted

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

def convert(s, m, n):
  if s == "H":
    return 0
  if s == "D":
    return 1
  if s[0] == "C":
    return int(s[1:]) + 1
  if s[0] == "L":
    return int(s[1:]) + m + 1

def get_cost(start, m, n, edges):
  cost = [INF] * (m + n + 2)
  cost[start] = 0
  que = []
  heappush(que, (0, start))
  while que:
    total, node = heappop(que)
    for dist, to in edges[node]:
      if cost[to] > total + dist:
        cost[to] = total + dist
        if not (2 <= to <= m + 1):
          heappush(que, (total + dist, to))
  return cost


def shortest_path(start, goal, rest, cakes_dist, dic):
  if not rest:
    return cakes_dist[start][goal]
  #if (start, rest) in dic:
  #  return dic[(start, rest)]
  
  ret = INF
  for to in rest:
    ret = min(ret, shortest_path(to, goal, tuple((i for i in rest if i != to)), cakes_dist, dic) + cakes_dist[start][to])
  dic[(start, rest)] = ret
  return ret

while True:
  m, n, k, d = map(int, input().split())
  if m == 0:
    break
  clst = list(map(int, input().split()))
  """
  Home ... 0
  D ... 1
  Cake ... 2, 3, ... m + 1
  Land ... m + 2, m + 3, ... m + n + 1
  """
  edges = [[] for _ in range(m + n + 2)]
  for _ in range(d):
    s, t, e = input().split()
    e = int(e)
    s = convert(s, m, n)
    t = convert(t, m, n)
    edges[s].append((e, t))
    edges[t].append((e, s))
  
  cakes_dist = [[INF] * (m + 2) for _ in range(m + 2)]
  for start in range(m + 2):
    cost = get_cost(start, m, n, edges)
    for to in range(m + 2):
      if to != start:
        cakes_dist[start][to] = cost[to]
  
  """
  now ... 現在いる点
  rest ... 残りのめぐる点
  dic[(now, rest)] ... 現在いる点、残りの点をまわる時の最小距離
  dic[(now, rest)] = min(cakes_dist[now][to] + dic[(to, rest - to)] for to in rest)
  """
  dic = {}
  ans = INF
  cakes = [i for i in range(2, m + 2)]
  for num in range(m + 1):
    for rest in combinations(cakes, num):
      cal = sum([clst[i - 2] for i in rest])
      ans = min(ans, shortest_path(0, 1, rest, cakes_dist, dic) * k - cal)
  print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
INF = 10**18
while 1:
    M, N, K, D = map(int, input().split())
    if M == N == K == D == 0:
        break
    *C, = map(int, input().split())
    def convert(s):
        if s == 'H':
            return 0
        if s[0] == 'C':
            return int(s[1:])
        if s[0] == 'L':
            return M+int(s[1:])
        return 1+N+M
    G = [[] for i in range(N+M+2)]
    H = [-1]*(N+M+2)
    for i in range(M):
        H[i+1] = i
    for i in range(D):
        s, t, e = input().split()
        s = convert(s); t = convert(t)
        e = int(e)
        G[s].append((t, e))
        G[t].append((s, e))

    dist = [[INF]*(1 << 6) for i in range(N+M+2)]
    que = [(0, 0, 0)]
    while que:
        cost, state, v = heappop(que)
        if dist[v][state] < cost:
            continue
        for w, e in G[v]:
            d = cost + e*K; n_state = state
            if H[w] != -1:
                if state & (1 << H[w]):
                    continue
                n_state |= (1 << H[w])
                d -= C[H[w]]
            if d < dist[w][n_state]:
                dist[w][n_state] = d
                heappush(que, (d, n_state, w))
    print(min(dist[N+M+1]))

Submission status: Runtime Error

Solution code:
import Queue
INF = 1 << 29
class Edge:
    def __init__(self, _v, _cost):
        self.v = _v
        self.cost = _cost
def parse(s, m, n):
    if(s[0]=="C"): return int(s.translate(None, "C")) - 1
    elif(s[0]=="L"): return int(s.translate(None, "L")) - 1 + m
    elif(s[0]=="H"): return m + n 
    else: return m + n + 1
while True:
    m, n, k, d = map(int, raw_input().split())
    if m==0 and n==0 and k==0 and d==0: break
    cake = map(int, raw_input().split())
    G = [[]*(m + n + 2) for i in range((m + n + 2))]
    for i in range(d):
        dist = raw_input().split()
        u = parse(dist[0], m, n)
        v = parse(dist[1], m ,n)
        G[v].append(Edge(u, int(dist[2])))
        G[u].append(Edge(v, int(dist[2])))
    D = [[0  for col in range(108)]  for row in range(1<<6)]
    for i in range(m + n + 2):
        for j in range(1 << m):
            D[i][j] = INF
    D[m + n][0] = 0
    ans = INF
    que = Queue.PriorityQueue()
    que.put([0, [m + n, 0]])
    while not que.empty():
        item = que.get()
        d_now = -item[0]
        u = item[1][0]
        s = item[1][1]
        if D[u][s] < d_now: continue
        if u == m + n + 1: ans = min(ans, d_now)
        for i in range(len(G[u])):
            v = G[u][i].v
            if v < m:
                if s&1 << v != 0: continue
                s2 = s | 1 << v
                d2 = d_now + k * G[u][i].cost - cake[v]
            else :
                s2 = s
                d2 = d_now + k * G[u][i].cost
            if d2 < D[v][s2]:
                D[v][s2] = d2
                que.put([-d2, [v, s2]])
    print ans

Submission status: Runtime Error

Solution code:
import Queue
INF = 1 << 29
class Edge:
    def __init__(self, _v, _cost):
        self.v = _v
        self.cost = _cost
def parse(s, m, n):
    if(s[0]=="C"): return int(s.translate(None, "C")) - 1
    elif(s[0]=="L"): return int(s.translate(None, "L")) - 1 + m
    elif(s[0]=="H"): return m + n 
    else: return m + n + 1
while True:
    m, n, k, d = map(int, raw_input().split())
    if m==0 and n==0 and k==0 and d==0: break
    cake = map(int, raw_input().split())
    G = [[] for i in range((m + n + 2))]
    for i in range(d):
        dist = raw_input().split()
        u = parse(dist[0], m, n)
        v = parse(dist[1], m ,n)
        G[v].append(Edge(u, int(dist[2])))
        G[u].append(Edge(v, int(dist[2])))
    D = [[0  for col in range(108)]  for row in range(1<<6)]
    for i in range(m + n + 2):
        for j in range(1 << m):
            D[i][j] = INF
    D[m + n][0] = 0
    ans = INF
    que = Queue.PriorityQueue()
    que.put([0, [m + n, 0]])
    while not que.empty():
        item = que.get()
        d_now = -item[0]
        u = item[1][0]
        s = item[1][1]
        if D[u][s] < d_now: continue
        if u == m + n + 1: ans = min(ans, d_now)
        for i in range(len(G[u])):
            v = G[u][i].v
            if v < m:
                if s&1 << v != 0: continue
                s2 = s | 1 << v
                d2 = d_now + k * G[u][i].cost - cake[v]
            else :
                s2 = s
                d2 = d_now + k * G[u][i].cost
            if d2 < D[v][s2]:
                D[v][s2] = d2
                que.put([-d2, [v, s2]])
    print ans

Submission status: Runtime Error

Solution code:
import Queue
INF = 1 << 29
class Edge:
    def __init__(self, _v, _cost):
        self.v = _v
        self.cost = _cost
def parse(s, m, n):
    if(s[0]=="C"): return int(s.translate(None, "C")) - 1
    elif(s[0]=="L"): return int(s.translate(None, "L")) - 1 + m
    elif(s[0]=="H"): return m + n 
    else: return m + n + 1
while True:
    m, n, k, d = map(int, raw_input().split())
    if m==0 and n==0 and k==0 and d==0: break
    cake = map(int, raw_input().split())
    G = [[] for i in range(m + n + 2)]
    for i in range(d):
        dist = raw_input().split()
        u = parse(dist[0], m, n)
        v = parse(dist[1], m ,n)
        G[v].append(Edge(u, int(dist[2])))
        G[u].append(Edge(v, int(dist[2])))
    D = [[0  for col in range(1<<6)]  for row in range(108)]
    for i in range(m + n + 2):
        for j in range(1 << m):
            D[i][j] = INF
    D[m + n][0] = 0
    ans = INF
    que = Queue.PriorityQueue()
    que.put([0, [m + n, 0]])
    while not que.empty():
        item = que.get()
        d_now = -item[0]
        u = item[1][0]
        s = item[1][1]
        if D[u][s] < d_now: continue
        if u == m + n + 1: ans = min(ans, d_now)
        for i in range(len(G[u])):
            v = G[u][i].v
            if v < m:
                if s&1 << v != 0: continue
                s2 = s | 1 << v
                d2 = d_now + k * G[u][i].cost - cake[v]
            else :
                s2 = s
                d2 = d_now + k * G[u][i].cost
            if d2 < D[v][s2]:
                D[v][s2] = d2
                que.put([-d2, [v, s2]])
    print ans