47. 参加科学大会（第六期模拟笔试）
import queueclass Edge:def __init__(self, t, w):self.t = t self.w = w def main():n, m = map(int, input().split())grid = [[] for _ in range(n + 1)]for _ in range(m):s, t, w = map(int, input().split())grid[s].append(Edge(t, w))minDist = [float('inf')] * (n + 1)visited = [False] * (n + 1)pq = queue.PriorityQueue()pq.put((0, 1))minDist[1] = 0while not pq.empty():cur_dist, cur = pq.get()if visited[cur]:continuevisited[cur] = Truefor edge in grid[cur]:if not visited[edge.t] and edge.w + cur_dist < minDist[edge.t]:minDist[edge.t] = edge.w + cur_distpq.put((minDist[edge.t], edge.t))if minDist[n] == float('inf'):print(-1)else:print(minDist[n])if __name__=='__main__':main()
94. 城市间货物运输 I
def main():n, m = map(int, input().split())edges = [tuple(map(int, input().split())) for _ in range(m)]minDist = [float('inf')] * (n + 1)minDist[1] = 0for _ in range(n):updated = Falsefor s, t, w in edges:if minDist[s] != float('inf') and minDist[s] + w < minDist[t]:minDist[t] = minDist[s] + wupdated = Trueif not updated:breakif minDist[n] == float('inf'):print('unconnected')else:print(minDist[n])if __name__ == '__main__':main()