代码随想录算法训练营 Day 51

import heapq
from collections import defaultdict

if __name__ == '__main__':
    n, m = map(int, input().split())
    
    edge = defaultdict(list)
    for _ in range(m):
        s, e, v = map(int, input().split())
        edge[s].append((e, v))
    
    min_dist = [float('inf')] * (n + 1)
    visited = [False] * (n + 1)
    
    pq = []
    heapq.heappush(pq, (0, 1))
    min_dist[1] = 0
    
    while pq:
        curr_dist, curr_node = heapq.heappop(pq)
        
        if visited[curr_node]:
            continue
        
        visited[curr_node] = True
        
        for e, d in edge[curr_node]:
            if not visited[e] and curr_dist + d < min_dist[e]:
                min_dist[e] = curr_dist + d
                heapq.heappush(pq, (min_dist[e], e))
    
    print(min_dist[-1] if min_dist[-1] != float('inf') else -1)

if __name__ == '__main__':
    n, m = map(int, input().split())
    
    edges = []
    for _ in range(m):
        s, t, v = map(int, input().split())
        edges.append((s, t, v))
    
    min_dist = [float('inf')] * (n + 1)
    min_dist[1] = 0
    
    for _ in range(1, n):
        updated = False
        
        for src, tar, weight in edges:
            if min_dist[src] != float('inf') and min_dist[src] + weight < min_dist[tar]:
                min_dist[tar] = min_dist[src] + weight
                updated = True
                
        # 提前退出策略，当本次遍历不存在更新操作时，退出循环
        if not updated:
            break
    
    print(min_dist[-1] if min_dist[-1] != float('inf') else 'unconnected')