c.ManiacMoving.py 3.1 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104
  1. import numpy as np
  2. def directDist(i, j, ABG):
  3. dist = -1
  4. for A, B, G in ABG:
  5. if ((A == i and B == j) or (A == j and B == i)) and (dist == -1 or G < dist):
  6. dist = G
  7. return dist
  8. # From http://stackoverflow.com/a/22899400
  9. def shortest(i, j, ABG, nodes):
  10. # print("i={0}, j={1}, ABG={2}, nodes={3}".format(i, j, ABG, nodes))
  11. distances = {}
  12. for A, B, G in ABG:
  13. # print(distances)
  14. if A not in distances or B not in distances:
  15. distances[A] = {B: G}
  16. distances[B] = {A: G}
  17. continue
  18. if B not in distances[A]:
  19. distances[A][B] = G
  20. distances[B][A] = G
  21. continue
  22. if G < distances[A][B]:
  23. distances[A][B] = G
  24. distances[B][A] = G
  25. unvisited = {node: None for node in nodes} #using None as +inf
  26. visited = {}
  27. current = i
  28. currentDistance = 0
  29. unvisited[current] = currentDistance
  30. while True:
  31. for neighbour, distance in distances[current].items():
  32. if neighbour not in unvisited: continue
  33. newDistance = currentDistance + distance
  34. if unvisited[neighbour] is None or unvisited[neighbour] > newDistance:
  35. unvisited[neighbour] = newDistance
  36. visited[current] = currentDistance
  37. if current == j:
  38. return visited
  39. del unvisited[current]
  40. if not unvisited: break
  41. candidates = [node for node in unvisited.items() if node[1]]
  42. # print("unvisited", unvisited)
  43. # print("candidates", candidates)
  44. current, currentDistance = sorted(candidates, key = lambda x: x[1])[0]
  45. return visited
  46. def routes(ABG, SD):
  47. r = {}
  48. townsInSD = set()
  49. townsInABG = set()
  50. # We only compute the routes for towns in SD
  51. for S, D in SD:
  52. # print("S={0}, D={1}".format(S, D))
  53. townsInSD.add(S)
  54. townsInSD.add(D)
  55. for A, B, G in ABG:
  56. # print("A={0}, B={1}, G={2}".format(A, B, G))
  57. townsInABG.add(A)
  58. townsInABG.add(B)
  59. # print(townsInSD)
  60. # print(townsInABG)
  61. if len(townsInABG) < len(townsInSD):
  62. return {}
  63. allTowns = townsInSD | townsInABG
  64. # print("Shortest:", shortest(1, 2, ABG, allTowns))
  65. for i in townsInSD:
  66. for j in townsInSD:
  67. if (i,j) in r:
  68. continue
  69. shortst = shortest(i, j, ABG, allTowns)
  70. print("Shortest:", shortst)
  71. dist = shortst[j]
  72. r[(i,j)] = dist
  73. r[(j,i)] = dist
  74. return r
  75. def solve(N, M, K, ABG, SD):
  76. print("N={0}, M={1}, K={2}, ABG={3}, SD={4}".format(N, M, K, ABG, SD))
  77. if K <= 0:
  78. return 0
  79. r = routes(ABG, SD)
  80. print(r)
  81. if r == {}:
  82. return -1
  83. return 'gnagna'
  84. if __name__ == "__main__":
  85. import fileinput
  86. f = fileinput.input()
  87. T = int(f.readline())
  88. for case in range(1, T+1):
  89. N, M, K = [int(i) for i in f.readline().split()]
  90. ABG = [[int(i) for i in f.readline().split()] for x in range(M)]
  91. SD = [[int(i) for i in f.readline().split()] for x in range(K)]
  92. solution = solve(N, M, K, ABG, SD)
  93. print("Case #{0}: {1}".format(case, solution))