123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869 |
- 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))
|