题解 | #换乘#

#include <iostream>
#include <vector>
#include <unordered_map>
#include <climits>
using namespace std;

struct Edge {
    int from, to, weight;
    Edge(int f, int t, int w) : from(f), to(t), weight(w) {}
};

int main() {
    int end, n;
    cin >> end >> n;
    
    vector<Edge> edges;
    unordered_map<int, int> dist;
    
    // 读入边信息
    for (int i = 0; i < n; i++) {
        int s, e, w;
        cin >> s >> e >> w;
        edges.emplace_back(s, e, w);
        dist[s] = INT_MAX;
        dist[e] = INT_MAX;
    }
    
    // Bellman-Ford算法
    dist[0] = 0;
    while (true) {
        bool update = false;
        for (const Edge& e : edges) {
            if (dist[e.from] != INT_MAX && 
                dist[e.to] > dist[e.from] + e.weight) {
                dist[e.to] = dist[e.from] + e.weight;
                update = true;
            }
        }
        if (!update) break;
    }
    
    cout << (dist[end] == INT_MAX ? -1 : dist[end]) << endl;
    return 0;
}

import java.util.*;

public class Main {
    static class Edge {
        int from, to, weight;
        Edge(int from, int to, int weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int end = sc.nextInt();
        int n = sc.nextInt();
        
        Edge[] edges = new Edge[n];
        Map<Integer, Integer> dist = new HashMap<>();
        
        // 读入边信息
        for (int i = 0; i < n; i++) {
            int s = sc.nextInt();
            int e = sc.nextInt();
            int w = sc.nextInt();
            edges[i] = new Edge(s, e, w);
            dist.put(s, Integer.MAX_VALUE);
            dist.put(e, Integer.MAX_VALUE);
        }
        
        // Bellman-Ford算法
        dist.put(0, 0);
        while (true) {
            boolean update = false;
            for (Edge e : edges) {
                if (dist.get(e.from) != Integer.MAX_VALUE && 
                    dist.get(e.to) > dist.get(e.from) + e.weight) {
                    dist.put(e.to, dist.get(e.from) + e.weight);
                    update = true;
                }
            }
            if (!update) break;
        }
        
        System.out.println(dist.get(end) == Integer.MAX_VALUE ? -1 : dist.get(end));
    }
}

class Edge:
    def __init__(self, from_node, to_node, weight):
        self.from_node = from_node
        self.to_node = to_node
        self.weight = weight

# 读入数据
end, n = map(int, input().split())
edges = []
dist = {}

# 读入边信息
for _ in range(n):
    s, e, w = map(int, input().split())
    edges.append(Edge(s, e, w))
    dist[s] = float('inf')
    dist[e] = float('inf')

# Bellman-Ford算法
dist[0] = 0
while True:
    update = False
    for e in edges:
        if (dist[e.from_node] != float('inf') and 
            dist[e.to_node] > dist[e.from_node] + e.weight):
            dist[e.to_node] = dist[e.from_node] + e.weight
            update = True
    if not update:
        break

print(-1 if dist[end] == float('inf') else dist[end])