首解

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
struct Edge {
int to, cost;
Edge(int t, int c) : to(t), cost(c) {}
};
typedef pair<int, int> pii;
int main() {
int n, m;
cin >> n >> m;

vector<vector<Edge>> graph(n + 1);
for (int i = 0; i < m; ++i) {
    int a, b, c;
    cin >> a >> b >> c;
    graph[a].push_back(Edge(b, c));
    graph[b].push_back(Edge(a, c));
}
vector<int> dist(n + 1, INT_MAX);
dist[1] = 0;
priority_queue<pii, vector<pii>, greater<pii>> pq; 
pq.push({0, 1});
while (!pq.empty()) {
    int u = pq.top().second;
    int d = pq.top().first;
    pq.pop();
    
    if (d > dist[u]) continue;
    
    for (const Edge& e : graph[u]) {
        int v = e.to;
        int cost = e.cost;
        if (dist[u] + cost < dist[v]) {
            dist[v] = dist[u] + cost;
            pq.push({dist[v], v});
        }
    }
}
if (dist[n] == INT_MAX) {
    cout << -1 << endl;
} else {
    cout << dist[n] << endl;
}
return 0;

}链接描述