Submission #2835112

---

Source Code Expand

from collections import deque

N = int(input())
S = [input() for i in range(N)]
M = int(input())
src = [tuple(input().split()) for i in range(M)]
es = [[] for i in range(N)]
for a,b in src:
    u = S.index(a)
    v = S.index(b)
    es[u].append(v)
    es[v].append(u)

C = input()
D = input()
start = S.index(C)
goal = S.index(D)

ans = 'Z'*21
ans_dist = N
q = deque([(start, 0, 0, C)]) #v, v_visited, e_used, path_str
while q:
    v,visited,used,path = q.popleft()
    if v == start and visited & (1<<goal):
        dist = bin(visited).count('1')
        if dist > ans_dist: break
        ans_dist = dist
        ans_cand = path[:-len(C)]
        ans = min(ans, ans_cand)
    for to in es[v]:
        if visited & (1<<to): continue
        e = min(v,to)*N + max(v,to)
        if used & (1<<e): continue
        q.append((to, visited|(1<<to), used|(1<<e), path+S[to]))
print(ans)

Submission Info

Judge Result