豆包题解 | 嘉豪舞团

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

int main() {
    int n, a, b;
    cin >> n >> a >> b;
    
    // 用哈希表存储邻接表，避免城市编号过大的问题
    unordered_map<int, vector<pair<int, int>>> adj;
    
    // 读取所有边，构建邻接表（无向图）
    for (int i = 0; i < n; ++i) {
        int p, q, x;
        cin >> p >> q >> x;
        adj[p].push_back({q, x});
        adj[q].push_back({p, x});
    }
    
    // Dijkstra算法：用哈希表存储距离，初始化为无穷大
    unordered_map<int, long long> dist;
    // 优先队列（最小堆）：(距离, 节点)
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq;
    
    // 初始化起点距离
    dist[a] = 0;
    pq.push({0, a});
    
    while (!pq.empty()) {
        auto [current_dist, u] = pq.top();
        pq.pop();
        
        // 若当前距离大于已知最短距离，跳过
        if (current_dist > dist[u]) continue;
        
        // 遍历邻接节点（若u不在邻接表中，说明无邻居）
        for (auto [v, weight] : adj[u]) {
            long long new_dist = current_dist + weight;
            // 若v未被访问过，或发现更短路径
            if (!dist.count(v) || new_dist < dist[v]) {
                dist[v] = new_dist;
                pq.push({new_dist, v});
            }
        }
    }
    
    // 输出结果：检查b是否可达
    if (dist.count(b) && dist[b] != LLONG_MAX) {
        cout << dist[b] << endl;
    } else {
        cout << -1 << endl;
    }
    
    return 0;
}