c.ManiacMoving.py 1.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172
  1. import numpy as np
  2. def shortest(i, j, ABG):
  3. visited = {}
  4. level = 0
  5. while True:
  6. L[level] = {}
  7. for A, B, G in ABG:
  8. if A != i and B != i:
  9. continue
  10. if A == i:
  11. x = B
  12. else:
  13. x = A
  14. if x not in L[level] or L[level][x] > G:
  15. L[level][x] = G
  16. direct = -1
  17. if j in minis:
  18. direct = minis[j]
  19. for x, dist in enumerate(minis):
  20. if direct > dist:
  21. distToJ = shortest(x, j, ABG)
  22. if distToJ < ...
  23. def routes(ABG, SD):
  24. r = {}
  25. townsInSD = set()
  26. townsInABG = set()
  27. # We only compute the routes for towns in SD
  28. for S, D in SD:
  29. # print("S={0}, D={1}".format(S, D))
  30. townsInSD.add(S)
  31. townsInSD.add(D)
  32. for A, B, G in ABG:
  33. # print("A={0}, B={1}, G={2}".format(A, B, G))
  34. townsInABG.add(A)
  35. townsInABG.add(B)
  36. print(townsInSD)
  37. print(townsInABG)
  38. if len(townsInABG) < len(townsInSD):
  39. return {}
  40. allTowns = townsInSD | townsInABG
  41. for i in townsInSD:
  42. for j in townsInSD:
  43. if (i,j) in r:
  44. continue
  45. dist = shortest(i, j, ABG)
  46. r[(i,j)] = dist
  47. r[(j,i)] = dist
  48. return r
  49. def solve(N, M, K, ABG, SD):
  50. print("N={0}, M={1}, K={2}, ABG={3}, SD={4}".format(N, M, K, ABG, SD))
  51. if K <= 0:
  52. return 0
  53. r = routes(ABG, SD)
  54. if r == {}:
  55. return -1
  56. return 'gnagna'
  57. if __name__ == "__main__":
  58. import fileinput
  59. f = fileinput.input()
  60. T = int(f.readline())
  61. for case in range(1, T+1):
  62. N, M, K = [int(i) for i in f.readline().split()]
  63. ABG = [[int(i) for i in f.readline().split()] for x in range(M)]
  64. SD = [[int(i) for i in f.readline().split()] for x in range(K)]
  65. solution = solve(N, M, K, ABG, SD)
  66. print("Case #{0}: {1}".format(case, solution))