Bessie Come Home

def pathfind(adjList,start,end):
    q = []
    dist = {}
    prev = {}

    for pasture in adjList.keys():
        dist[pasture]=float('inf')
        prev[pasture]=None
        q.append(pasture)
    dist[start] = 0

    while any(q):
        min = float('inf')
        u = None
        for j in q:
            if j != None:
                if dist[j] < min:
                    min = dist[j]
                    u = j
        if u == None: return -1 # No paths
        if u == end:
            s = []
            d = dist[end]
            if prev[u] != None or u == start:
                while u != None:
                    s.insert(0,u)
                    u = prev[u]
                print(s,d)
                return d

        for connectedPasture in adjList[u]:
            if connectedPasture[0] != None:
                alt = dist[u] + connectedPasture[1]
                if alt < dist[connectedPasture[0]]:
                    dist[connectedPasture[0]] = alt
                    prev[connectedPasture[0]] = u
        q[q.index(u)] = None

def run(adjList):
    recordCow = ''
    recordDistance = float('inf')
    for cow in adjList.keys():
        if cow.isupper() and cow != 'Z':
            d = pathfind(adjList,cow,'Z')
            if d < recordDistance and d != -1:
                recordCow = cow
                recordDistance = d
    return recordCow, recordDistance

def main():
    with open('comehome.in','r') as fIn:
        f = fIn.read().split('\n')[1:-1]
    adjList = {}
    for i in 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz': # initialize adjList
        adjList[i] = []
    for k in f:
        k = k.split()
        adjList[k[0]].append([k[1],int(k[2])])
        adjList[k[1]].append([k[0],int(k[2])])
    res = run(adjList)
    print(res)
    with open('comehome.out','w') as fOut:
        fOut.write('%s %d\n'%(res[0],res[1]))

if __name__ == '__main__': main()