M05443: 兔子与樱花
dijkstra, Floyd-Warshall, http://cs101.openjudge.cn/practice/05443/
很久很久之前，森林里住着一群兔子。有一天，兔子们希望去赏樱花，但当他们到了上野公园门口却忘记了带地图。现在兔子们想求助于你来帮他们找到公园里的最短路。
输入
输入分为三个部分。 第一个部分有P+1行（P<30），第一行为一个整数P，之后的P行表示上野公园的地点, 字符串长度不超过20。 第二个部分有Q+1行（Q<50），第一行为一个整数Q，之后的Q行每行分别为两个字符串与一个整数，表示这两点有直线的道路，并显示二者之间的矩离（单位为米）。 第三个部分有R+1行（R<20），第一行为一个整数R，之后的R行每行为两个字符串，表示需要求的路线。
输出
输出有R行，分别表示每个路线最短的走法。其中两个点之间，用->(矩离)->相隔。
样例输入
6
Ginza
Sensouji
Shinjukugyoen
Uenokouen
Yoyogikouen
Meijishinguu
6
Ginza Sensouji 80
Shinjukugyoen Sensouji 40
Ginza Uenokouen 35
Uenokouen Shinjukugyoen 85
Sensouji Meijishinguu 60
Meijishinguu Yoyogikouen 35
2
Uenokouen Yoyogikouen
Meijishinguu Meijishinguu样例输出
Uenokouen->(35)->Ginza->(80)->Sensouji->(60)->Meijishinguu->(35)->Yoyogikouen
Meijishinguu由于图中所有边的权值均为非负数，可以利用经典的 Dijkstra 算法：维护一个全局的距离字典，当发现更短的路径时更新之。
python
import heapq
from collections import defaultdict
p = int(input())
points = [input().strip() for _ in range(p)]
maps = defaultdict(list)
for _ in range(int(input())):
a, b, d = input().split()
d = int(d)
maps[a].append((b, d))
maps[b].append((a, d))
def dijkstra(src, dst):
INF = float('inf')
dist = {point: INF for point in points}
path = {point: "" for point in points}
dist[src] = 0
path[src] = src
pq = [(0, src)]
while pq:
d, u = heapq.heappop(pq)
if d > dist[u]:
continue
if u == dst:
break
for v, w in maps[u]:
nd = d + w
if nd < dist[v]:
dist[v] = nd
path[v] = path[u] + f"->({w})->" + v
heapq.heappush(pq, (nd, v))
return path[dst]
for _ in range(int(input())):
s, t = input().split()
print(dijkstra(s, t))【柯有为】思路：图的最短路径问题，用Dijkstra方法。由于是求最短路径，所以需要额外添加一个储存路径的字典，最后将路径转化为所要求的格式输出即可。
python
import heapq
def Dijkstra(graph, start, end):
if start == end:
return []
distances = {place:float('inf') for place in graph.keys()}
paths = {place:[] for place in graph.keys()}
distances[start] = 0
heap = []
heapq.heappush(heap, (0, [], start))
while heap:
d, path, cur = heapq.heappop(heap)
for neighbor, nd in graph[cur].items():
if d + nd < distances[neighbor]:
distances[neighbor] = d + nd
paths[neighbor] = path + [neighbor]
heapq.heappush(heap, (distances[neighbor], paths[neighbor], neighbor))
return paths[end]
graph = dict()
P = int(input())
for _ in range(P):
graph[input()] = dict()
Q = int(input())
for _ in range(Q):
u, v, d = map(str,input().split())
graph[u][v] = graph[v][u] = int(d)
R = int(input())
for _ in range(R):
start, end = map(str,input().split())
path = Dijkstra(graph, start, end)
output = start
cur = start
for vertex in path:
output += f"->({graph[cur][vertex]})->{vertex}"
cur = vertex
print(output)思路：多添加一个路径进入pos即可。
python
# 谭琳诗倩、2200013722
import heapq
import math
def dijkstra(graph,start,end,P):
if start == end: return []
dist = {i:(math.inf,[]) for i in graph}
dist[start] = (0,[start])
pos = []
heapq.heappush(pos,(0,start,[]))
while pos:
dist1,current,path = heapq.heappop(pos)
for (next,dist2) in graph[current].items():
if dist2+dist1 < dist[next][0]:
dist[next] = (dist2+dist1,path+[next])
heapq.heappush(pos,(dist1+dist2,next,path+[next]))
return dist[end][1]
P = int(input())
graph = {input():{} for _ in range(P)}
for _ in range(int(input())):
place1,place2,dist = input().split()
graph[place1][place2] = graph[place2][place1] = int(dist)
for _ in range(int(input())):
start,end = input().split()
path = dijkstra(graph,start,end,P)
s = start
current = start
for i in path:
s += f'->({graph[current][i]})->{i}'
current = i
print(s)【曹以楷 24物理学院】思路：Floyd-Warshall
python
from itertools import product
from typing import List
class Solution:
INF = 1 << 30
def solve(self) -> None:
n = int(input())
locations = [input().strip() for _ in range(n)]
distances = [[self.INF] * n for _ in range(n)]
next_node = [[-1] * n for _ in range(n)]
# 初始化自身到自身的距离为 0
for i in range(n):
distances[i][i] = 0
# 读取边信息并初始化邻接矩阵和路径表
for _ in range(int(input())):
a, b, d = input().split()
u, v, dist = locations.index(a), locations.index(b), int(d)
if dist < distances[u][v]:
distances[u][v] = distances[v][u] = dist
next_node[u][v] = v
next_node[v][u] = u
# Floyd-Warshall 算法计算所有点对最短路径
for k, i, j in product(range(n), repeat=3):
if distances[i][j] > distances[i][k] + distances[k][j]:
distances[i][j] = distances[i][k] + distances[k][j]
next_node[i][j] = next_node[i][k]
# 查询路径
for _ in range(int(input())):
a, b = input().split()
u, v = locations.index(a), locations.index(b)
if distances[u][v] == self.INF:
print("No path")
else:
print(self.reconstruct_path(next_node, u, v, locations, distances))
def reconstruct_path(self, next_node: List[List[int]],
u: int, v: int, locations: List[str], distances: List[List[int]]) -> str:
path_indices = [u]
while u != v:
u = next_node[u][v]
path_indices.append(u)
# 构造格式化路径字符串
result = locations[path_indices[0]]
for i in range(1, len(path_indices)):
from_idx, to_idx = path_indices[i - 1], path_indices[i]
result += f"->({distances[from_idx][to_idx]})->{locations[to_idx]}"
return result
if __name__ == "__main__":
Solution().solve()【张俊龙 24工学院】思路：定义最小距离以及走最小距离的第一步，之后三重循环维护。
代码的功能是：实现一个带权无向图的最短路径查询系统，它会先读入点和边的信息，预处理所有点对之间的最短路径（使用 Floyd-Warshall 算法），然后支持多次查询输出从一个点到另一个点的路径和路径长度。
python
def floyd_warshall(p, length, nxt):
for k in range(p):
for i in range(p):
if length[i][k] == float('inf'):
continue
for j in range(p):
if length[k][j] == float('inf'):
continue
if length[i][k] + length[k][j] < length[i][j]:
length[i][j] = length[i][k] + length[k][j]
nxt[i][j] = nxt[i][k]
def reconstruct_path(u, v, nxt, name, length):
if u == v:
return name[u]
path = [u]
while u != v:
u = nxt[u][v]
if u is None:
return "NO PATH"
path.append(u)
result = name[path[0]]
for i in range(1, len(path)):
result += f'->({length[path[i - 1]][path[i]]})->{name[path[i]]}'
return result
# -------------------------------
# Main
# -------------------------------
p = int(input())
name = []
di = {}
for i in range(p):
place = input().strip()
name.append(place)
di[place] = i
length = [[float('inf')] * p for _ in range(p)]
nxt = [[None] * p for _ in range(p)]
for i in range(p):
length[i][i] = 0
nxt[i][i] = i
q = int(input())
for _ in range(q):
a, b, c = input().split()
u, v, d = di[a], di[b], int(c)
if d < length[u][v]: # Take shortest if multiple edges
length[u][v] = length[v][u] = d
nxt[u][v] = v
nxt[v][u] = u
# Compute all-pairs shortest paths
floyd_warshall(p, length, nxt)
r = int(input())
for _ in range(r):
a, b = input().split()
u, v = di[a], di[b]
print(reconstruct_path(u, v, nxt, name, length))floyd_warshall(...)：
- 经典三重循环版本。
- 如果从
i到j可以通过中间点k走得更短，则更新路径和nxt[i][j]。
reconstruct_path(...)：
- 利用
nxt重建路径。 - 输出格式为：
A->(距离)->B->(距离)->C。
思路：用
简单讲解该算法：