c.ManiacMoving.py 1.8 KB

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