Advertisement
Guest User

Untitled

a guest
Jun 18th, 2019
65
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.99 KB | None | 0 0
  1. import heapq
  2. import sys
  3. import math
  4. sys.setrecursionlimit(10000)
  5. INF = 999999999
  6. class Point:
  7. def __init__(self, x, y):
  8. self.x = float(x)
  9. self.y = float(y)
  10. def getCost(p,c):
  11. x_dis = abs(p.x - c.x)
  12. y_dis = abs(p.y - c.y)
  13. cost = math.sqrt(x_dis * x_dis + y_dis * y_dis)
  14. return cost
  15. def dijkstra(G, start, endp):
  16. dis = dict((point, INF) for point in G)
  17. dis[start] = 0.00
  18. vis = dict((point, False) for point in G)
  19. # heap
  20. pq = []
  21. heapq.heappush(pq, [dis[start], start])
  22. path = dict((point, [start]) for point in G)
  23. while len(pq) > 0:
  24. v_dis, v = heapq.heappop(pq)
  25. if vis[v] == True:
  26. continue
  27. vis[v] = True
  28. p = path[v].copy()
  29. for point in G:
  30. distance = getCost(v,point)
  31. if distance > 100.00:
  32. continue
  33. new_dis = dis[v] + distance
  34.  
  35. if new_dis < dis[point] and (not vis[point]):
  36. dis[point] = new_dis
  37.  
  38. heapq.heappush(pq, [dis[point], point])
  39. temp = p.copy()
  40. temp.append(point)
  41. path[point] = temp
  42. distance = dis[endp]
  43. if distance == INF:
  44. print("-1")
  45. else:
  46. print("{:.2f}".format(distance))
  47.  
  48. while True:
  49. try:
  50. numbers = input().strip().split(",")
  51. limit = int(numbers[0])
  52. point_list = []
  53. numbers = list(map(float, numbers))
  54. stap = Point(numbers[1],numbers[2])
  55. endp = Point(numbers[-2],numbers[-1])
  56. if stap.x>limit or stap.y>limit or stap.x<0 or stap.y<0 :
  57. print("-1")
  58. elif endp.x>limit or endp.y>limit or endp.x<0 or endp.y<0 :
  59. print("-1")
  60. else:
  61. for i in range(1, len(numbers), 2):
  62. if numbers[i]<=limit and numbers[i+1]<=limit:
  63. point_list.append(Point(numbers[i], numbers[i+1]))
  64. dijkstra(point_list, point_list[0], point_list[-1])
  65. except EOFError:
  66. break
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement