123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104 |
- import numpy as np
- def directDist(i, j, ABG):
- dist = -1
- for A, B, G in ABG:
- if ((A == i and B == j) or (A == j and B == i)) and (dist == -1 or G < dist):
- dist = G
- return dist
- # From http://stackoverflow.com/a/22899400
- def shortest(i, j, ABG, nodes):
- # print("i={0}, j={1}, ABG={2}, nodes={3}".format(i, j, ABG, nodes))
- distances = {}
- for A, B, G in ABG:
- # print(distances)
- if A not in distances or B not in distances:
- distances[A] = {B: G}
- distances[B] = {A: G}
- continue
- if B not in distances[A]:
- distances[A][B] = G
- distances[B][A] = G
- continue
- if G < distances[A][B]:
- distances[A][B] = G
- distances[B][A] = G
- unvisited = {node: None for node in nodes} #using None as +inf
- visited = {}
- current = i
- currentDistance = 0
- unvisited[current] = currentDistance
- while True:
- for neighbour, distance in distances[current].items():
- if neighbour not in unvisited: continue
- newDistance = currentDistance + distance
- if unvisited[neighbour] is None or unvisited[neighbour] > newDistance:
- unvisited[neighbour] = newDistance
- visited[current] = currentDistance
- if current == j:
- return visited
- del unvisited[current]
- if not unvisited: break
- candidates = [node for node in unvisited.items() if node[1]]
- # print("unvisited", unvisited)
- # print("candidates", candidates)
- current, currentDistance = sorted(candidates, key = lambda x: x[1])[0]
- return visited
- 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
- # print("Shortest:", shortest(1, 2, ABG, allTowns))
- for i in townsInSD:
- for j in townsInSD:
- if (i,j) in r:
- continue
- shortst = shortest(i, j, ABG, allTowns)
- print("Shortest:", shortst)
- dist = shortst[j]
- 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)
- print(r)
- 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))
|