hacker-cup/2017.1-RoundOne/c.ManiacMoving.py

import numpy as np

def shortest(i, j, ABG):
    minis = {}
    for A, B, G in ABG:
        if A != i and B != i:
            continue
        if A == i:
            x = B
        else:
            x = A
        if x not in minis or minis[x] > G:
            minis[x] = G
    direct = -1
    if j in minis:
        direct = minis[j]
    for x, dist in enumerate(minis):
        if direct > dist:
            distToJ = shortest(x, j, ABG)
        if distToJ < ...

def routes(ABG, SD):
    r = {}
    townsInSD = set()
    townsInABG = set()
    # We only compute the routes for towns in SD
    for S, D in SD:
        # print("S={0}, D={1}".format(S, D))
        townsInSD.add(S)
        townsInSD.add(D)
    for A, B, G in ABG:
        # print("A={0}, B={1}, G={2}".format(A, B, G))
        townsInABG.add(A)
        townsInABG.add(B)
    print(townsInSD)
    print(townsInABG)
    if len(townsInABG) < len(townsInSD):
        return {}
    allTowns = townsInSD | townsInABG
    for i in townsInSD:
        for j in townsInSD:
            if (i,j) in r:
                continue
            dist = shortest(i, j, ABG)
            r[(i,j)] = dist
            r[(j,i)] = dist
    return r

def solve(N, M, K, ABG, SD):
    print("N={0}, M={1}, K={2}, ABG={3}, SD={4}".format(N, M, K, ABG, SD))
    if K <= 0:
        return 0
    r = routes(ABG, SD)
    if r == {}:
        return -1
    return 'gnagna'

if __name__ == "__main__":
    import fileinput
    f = fileinput.input()

    T = int(f.readline())
    for case in range(1, T+1):
        N, M, K = [int(i) for i in f.readline().split()]
        ABG = [[int(i) for i in f.readline().split()] for x in range(M)]
        SD = [[int(i) for i in f.readline().split()] for x in range(K)]
        solution = solve(N, M, K, ABG, SD)
        print("Case #{0}: {1}".format(case, solution))