有没有老哥帮我看一看代码啊,dijkstra 实现最短路径的问题.

100,0,0,0,100,100,100
1000,20.892,986,602,138.97,206.2,10.44
200,25,25,10,1,50,25,140,30
输入格式是这样,每一行第一个数是地图限制,100 就说明这张图是 100x100,后面的点两两组合,第一个点(0,0)就是起点,最后一个点(100,100)就是终点,中间的点是可以去的城镇.
程序是模拟一个无人机从起点出发去往终点,最大移动距离 100,点与点之间移动举例按 math.sqrt(x_dis * x_dis + y_dis * y_dis)也就是欧几里得距离算.
如果点超出移动距离或者不在地图范围内是不算的.
案例输入的输出是
200.00
-1
115.14
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

在一个黑箱运行测试输入显示部分答案错误,一共五个案例,我只有 1,2 是全对,3,4,5 正确率越来越低.
现在我的代码在本地能很好的输出答案,只好猜测是不是逻辑出了问题,有老哥帮忙看一下的话感激不尽!

wcavell

2019-06-07 13:48:18 +08:00

@huiyifyj 我已经上传了 gist 的版本,我试试看吧
```python
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
```