シンプルなダイクストラの実装です。
本質部分の実装はわずか14行で済んでいます。
#include <bits/stdc++.h> using namespace std; const long long INF = 1e18; struct Edge { int to, cost; Edge(int to, int cost) : to(to), cost(cost) {} }; int main() { int n, m; cin >> n >> m; vector<vector<Edge>> g(n); for (int i = 0; i < m; i++) { int v, u, cost; cin >> v >> u >> cost; v--, u--; g[v].emplace_back(u, cost); g[u].emplace_back(v, cost); } using P = pair<long long, int>; priority_queue<P, vector<P>, greater<P>> q; vector<long long> dp(n, INF); q.emplace(0, 0); while (q.size()) { long long cost; int v; tie(cost, v) = q.top(); q.pop(); if (dp[v] != INF) { continue; } dp[v] = cost; for (auto e : g[v]) { q.emplace(cost + e.cost, e.to); } } for (int i = 0; i < n; i++) { cout << dp[i] << endl; } return 0; }