Buggy python submission (verdict: Runtime Error):
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

Fixed submission:
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

Buggy python submission (verdict: Runtime Error):
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

Fixed submission:
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

Buggy python submission (verdict: Runtime Error):
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

Fixed submission:
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