day_60
94. 城市间货物运输 I
from collections import dequeclass Edge:def __init__(self, to, val):self.to = to # 边指向的节点self.val = val # 边的权重def main():n, m = map(int, input().split())edges = [tuple(map(int, input().split())) for _ in range(m)]# 创建图的邻接表表示grid = [[] for _ in range(n + 1)]for s, t, w in edges:grid[s].append(Edge(t, w))minDist = [float('inf')] * (n + 1)minDist[1] = 0isInQueue = [False] * (n + 1)# 使用队列来存储需要松弛的节点que = deque()que.append(1)isInQueue[1] = Truewhile que:node = que.popleft()isInQueue[node] = Falsefor edge in grid[node]:if minDist[edge.to] > minDist[node] + edge.val:minDist[edge.to] = minDist[node] + edge.valif not isInQueue[edge.to]:que.append(edge.to)isInQueue[edge.to] = Trueif minDist[n] == float('inf'):print('unconnected')else:print(minDist[n])if __name__ == '__main__':main()95. 城市间货物运输 II
import sysdef main():input = sys.stdin.readdata = input().split()index = 0n = int(data[index])index += 1m = int(data[index])index += 1grid = []for i in range(m):p1 = int(data[index])index += 1p2 = int(data[index])index += 1val = int(data[index])index += 1# p1 指向 p2，权值为 valgrid.append([p1, p2, val])start = 1 # 起点end = n # 终点minDist = [float('inf')] * (n + 1)minDist[start] = 0flag = Falsefor i in range(1, n + 1): # 这里我们松弛n次，最后一次判断负权回路for side in grid:from_node = side[0]to = side[1]price = side[2]if i < n:if minDist[from_node] != float('inf') and minDist[to] > minDist[from_node] + price:minDist[to] = minDist[from_node] + priceelse: # 多加一次松弛判断负权回路if minDist[from_node] != float('inf') and minDist[to] > minDist[from_node] + price:flag = Trueif flag:print("circle")elif minDist[end] == float('inf'):print("unconnected")else:print(minDist[end])if __name__ == "__main__":main()这个代码风格不是我的风格，有空修改一下。
96. 城市间货物运输 III
N, M = list(map(int, input().split()))def main(N, M):minDest = [float('inf')] * (N+1)hashmap = []for _ in range(M):start, end, val = list(map(int, input().split()))hashmap.append([start, end, val])src, dst, k = list(map(int, input().split()))minDest[src] = 0for _ in range(k+1):minDest_copy = minDest.copy()flag = Falsefor edge in hashmap:start, end, val = edgeif minDest_copy[start] != float('inf') and minDest_copy[start] + val < minDest[end]:minDest[end] = minDest_copy[start] + valflag = Trueif flag == False:breakif minDest[dst] == float('inf'):print('unreachable')else:print(minDest[dst])returnmain(N, M)
这个同样。