Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import heapq
- import sys
- import math
- sys.setrecursionlimit(10000)
- INF = 999999999
- class Point:
- def __init__(self, x, y):
- self.x = float(x)
- self.y = float(y)
- def getCost(p,c):
- x_dis = abs(p.x - c.x)
- y_dis = abs(p.y - c.y)
- cost = math.sqrt(x_dis * x_dis + y_dis * y_dis)
- return cost
- def dijkstra(G, start, endp):
- dis = dict((point, INF) for point in G)
- dis[start] = 0.00
- vis = dict((point, False) for point in G)
- # heap
- pq = []
- heapq.heappush(pq, [dis[start], start])
- path = dict((point, [start]) for point in G)
- while len(pq) > 0:
- v_dis, v = heapq.heappop(pq)
- if vis[v] == True:
- continue
- vis[v] = True
- p = path[v].copy()
- for point in G:
- distance = getCost(v,point)
- if distance > 100.00:
- continue
- new_dis = dis[v] + distance
- if new_dis < dis[point] and (not vis[point]):
- dis[point] = new_dis
- heapq.heappush(pq, [dis[point], point])
- temp = p.copy()
- temp.append(point)
- path[point] = temp
- distance = dis[endp]
- if distance == INF:
- print("-1")
- else:
- print("{:.2f}".format(distance))
- while True:
- try:
- numbers = input().strip().split(",")
- limit = int(numbers[0])
- point_list = []
- numbers = list(map(float, numbers))
- stap = Point(numbers[1],numbers[2])
- endp = Point(numbers[-2],numbers[-1])
- if stap.x>limit or stap.y>limit or stap.x<0 or stap.y<0 :
- print("-1")
- elif endp.x>limit or endp.y>limit or endp.x<0 or endp.y<0 :
- print("-1")
- else:
- for i in range(1, len(numbers), 2):
- if numbers[i]<=limit and numbers[i+1]<=limit:
- point_list.append(Point(numbers[i], numbers[i+1]))
- dijkstra(point_list, point_list[0], point_list[-1])
- except EOFError:
- break
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement