神仙的仙居

class Graphic:
    def __init__(self):
        self.edges={}
    
    def join(self, a, b):
        if self.edges.has_key(a):
            self.edges[a]+=[b]
        else:
            self.edges[a]=[b]
        if self.edges.has_key(b):
            self.edges[b]+=[a]
        else:
            self.edges[b]=[a]
    
    def test(self, a, b):
        q=[]
        q.append(a)
        reaches={a:[]}
        while len(q) > 0:
            cur=q.pop(0)
            for n in self.edges[cur]:
                if n==cur:
                    continue
                if reaches.has_key(n) and len(reaches[n]) <= len(reaches[cur])+1:
                    continue
                if reaches.has_key(b) and len(reaches[b]) <= len(reaches[cur])+1:
                    continue
                q.append(n)
                reaches[n]=reaches[cur]+[cur]
        return reaches[b]+[b]

g=Graphic()

g.join(‘a’, ‘b’)
g.join(‘a’, ‘e’)
g.join(‘b’, ‘c’)
g.join(‘e’, ‘k’)
g.join(‘j’, ‘k’)
g.join(‘j’, ‘c’)
g.join(‘j’, ‘h’)
g.join(‘j’, ‘z’)
g.join(‘c’, ‘d’)
g.join(‘d’, ‘f’)
g.join(‘f’, ‘l’)
g.join(‘z’, ‘l’)

print g.test(‘a’,’d’)