02502: Subway
dijkstra, http://cs101.openjudge.cn/practice/02502/
You have just moved from a quiet Waterloo neighbourhood to a big, noisy city. Instead of getting to ride your bike to school every day, you now get to walk and take the subway. Because you don't want to be late for class, you want to know how long it will take you to get to school. You walk at a speed of 10 km/h. The subway travels at 40 km/h. Assume that you are lucky, and whenever you arrive at a subway station, a train is there that you can board immediately. You may get on and off the subway any number of times, and you may switch between different subway lines if you wish. All subway lines go in both directions.
输入
Input consists of the x,y coordinates of your home and your school, followed by specifications of several subway lines. Each subway line consists of the non-negative integer x,y coordinates of each stop on the line, in order. You may assume the subway runs in a straight line between adjacent stops, and the coordinates represent an integral number of metres. Each line has at least two stops. The end of each subway line is followed by the dummy coordinate pair -1,-1. In total there are at most 200 subway stops in the city.
输出
Output is the number of minutes it will take you to get to school, rounded to the nearest minute, taking the fastest route.
样例输入
0 0 10000 1000
0 200 5000 200 7000 200 -1 -1
2000 600 5000 600 10000 600 -1 -1样例输出
21来源
Waterloo local 2001.09.22
✅ 带注释的 Dijkstra 最短路径算法（支持步行与地铁）：
import math
import heapq
# 计算两点之间的欧几里得距离
def get_distance(x1, y1, x2, y2):
return math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)
# 读取起点（家）和终点（学校）坐标
sx, sy, ex, ey = map(int, input().split())
# min_time: 记录从起点到每个地铁站/终点的最短时间（单位：小时）
min_time = {}
# rails: 记录所有地铁连接（双向）
rails = set()
# 读取所有地铁线路
while True:
try:
rail = list(map(int, input().split()))
if rail == [-1, -1]:
break
# 解析当前地铁线路的所有站点
stations = [(rail[2 * i], rail[2 * i + 1]) for i in range(len(rail) // 2 - 1)]
for j, station in enumerate(stations):
# 初始化所有地铁站点的最短时间为无穷大
min_time[station] = float('inf')
# 添加地铁线路中相邻站点的双向连接
if j != len(stations) - 1:
rails.add((station, stations[j + 1]))
rails.add((stations[j + 1], station))
except EOFError:
break # 输入结束
# 把起点和终点加入时间表中
min_time[(sx, sy)] = 0 # 起点时间为 0
min_time[(ex, ey)] = float('inf') # 终点初始化为无穷大
# 使用小根堆实现 Dijkstra 算法，按时间升序处理节点
min_heap = [(0, sx, sy)] # (当前耗时, 当前x, 当前y)
while min_heap:
curr_time, x, y = heapq.heappop(min_heap)
# 如果当前耗时不是最短路径中记录的值，说明已经被更新，跳过
if curr_time > min_time[(x, y)]:
continue
# 如果已经到达终点，提前结束
if (x, y) == (ex, ey):
break
# 遍历所有可达点（隐式图）
for position in min_time.keys():
if position == (x, y):
continue # 自己跳过
nx, ny = position
# 计算当前位置到下一个点的距离
dis = get_distance(x, y, nx, ny)
# 判断是否为地铁连接：地铁速度是步行的4倍
rail_factor = 4 if ((position, (x, y)) in rails or ((x, y), position) in rails) else 1
# 计算到该点的所需时间（单位：小时）
new_time = curr_time + dis / (10000 * rail_factor)
# 如果时间更短，则更新并加入堆中
if new_time < min_time[position]:
min_time[position] = new_time
heapq.heappush(min_heap, (new_time, nx, ny))
# 输出从起点到终点的最短时间，转换为分钟并四舍五入
print(round(min_time[(ex, ey)] * 60))✅ 小结
- 地铁速度是步行的 4 倍 → 用
rail_factor = 4简化处理。 - 图是隐式图：所有站点间的连边不是预先建好，而是在 Dijkstra 中动态判断。
- 只对包含的点建图（避免不必要计算，提升效率）。
这个代码不仅简洁清晰，还容易维护和扩展，比如日后加入不同速度的公交车或地铁线路都很方便。
#2300012739 汤子瑜
import math
import heapq
def get_distance(x1, y1, x2, y2):
return math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)
sx, sy, ex, ey = map(int, input().split())
min_time = {}
rails = set()
while True:
try:
rail = list(map(int, input().split()))
if rail == [-1, -1]:
break
stations = [(rail[2 * i], rail[2 * i + 1]) for i in range(len(rail) // 2 - 1)]
for j, station in enumerate(stations):
min_time[station] = float('inf')
if j != len(stations) - 1:
rails.add((station, stations[j + 1]))
rails.add((stations[j + 1], station))
except EOFError:
break
min_time[(sx, sy)], min_time[(ex, ey)] = 0, float('inf')
min_heap = [(0, sx, sy)]
while min_heap:
curr_time, x, y = heapq.heappop(min_heap)
if curr_time > min_time[(x, y)]:
continue
if (x, y) == (ex, ey):
break
for position in min_time.keys():
if position == (x, y):
continue
nx, ny = position
dis = get_distance(x, y, nx, ny)
rail_factor = 4 if ((position, (x, y)) in rails or ((x, y), position) in rails) else 1
new_time = curr_time + dis / (10000 * rail_factor)
if new_time < min_time[position]:
min_time[position] = new_time
heapq.heappush(min_heap, (new_time, nx, ny))
print(round(min_time[(ex, ey)] * 60))import heapq
import math
def distance(x1, y1, x2, y2, speed):
return math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2) / speed
a, b, c, d = map(int, input().split())
home = (a, b)
school = (c, d)
# Subway stations and their coordinates
stations = [home, school]
subway_lines = []
# Reading the subway lines
while True:
try:
line = list(map(int, input().split()))
if line == [-1, -1]:
break
subway_line = []
for i in range(0, len(line) - 2, 2):
subway_line.append((line[i], line[i + 1]))
subway_lines.append(subway_line)
stations.extend(subway_line)
except EOFError:
break
# Number of stations
n = len(stations)
# Distance matrix
dis = [[float('inf')] * n for _ in range(n)]
# Walking distance
for i in range(n):
for j in range(i + 1, n):
dis[i][j] = dis[j][i] = distance(stations[i][0], stations[i][1], stations[j][0], stations[j][1], 10 / 3.6)
# Subway distance
for line in subway_lines:
for i in range(len(line) - 1):
u = stations.index(line[i])
v = stations.index(line[i + 1])
dis[u][v] = dis[v][u] = distance(line[i][0], line[i][1], line[i + 1][0], line[i + 1][1], 40 / 3.6)
# Dijkstra's algorithm
def dijkstra(start):
min_heap = [(0, start)]
min_time = [float('inf')] * n
min_time[start] = 0
while min_heap:
current_time, u = heapq.heappop(min_heap)
if current_time > min_time[u]:
continue
for v in range(n):
if u != v and current_time + dis[u][v] < min_time[v]:
min_time[v] = current_time + dis[u][v]
heapq.heappush(min_heap, (min_time[v], v))
return min_time
min_time = dijkstra(0)
print(round(min_time[1] / 60)) # Convert seconds to minutes and round to nearest minute