+C++20
The C++20 version stores integer costs in long long. Vertex indices and the start are valid, every weight is nonnegative, and each computed path sum is strictly below the maximum long long value. That maximum, INF, is reserved for unreachable vertices and is printed as Infinity to match TypeScript.
#include <cstddef>
#include <iostream>
#include <limits>
#include <vector>
using Distance = long long;
struct Edge { std::size_t to; Distance weight; };
using Graph = std::vector<std::vector<Edge>>;
constexpr Distance INF = std::numeric_limits<Distance>::max();
std::vector<Distance> dijkstra(const Graph& graph, std::size_t start) {
const auto n = graph.size();
std::vector<Distance> distance(n, INF);
std::vector<bool> settled(n, false);
distance[start] = 0;
for (std::size_t step = 0; step < n; ++step) {
auto from = n;
for (std::size_t vertex = 0; vertex < n; ++vertex) {
if (!settled[vertex] && (from == n || distance[vertex] < distance[from])) {
from = vertex;
}
}
// Stop when no reachable unsettled vertex remains.
if (from == n || distance[from] == INF) break;
settled[from] = true;
for (const auto& edge : graph[from]) {
if (settled[edge.to]) continue;
const auto candidate = distance[from] + edge.weight;
if (candidate < distance[edge.to]) distance[edge.to] = candidate;
}
}
return distance;
}
int main() {
// The vertex order is S, A, B, T, U.
const Graph graph{{{1, 4}, {2, 1}}, {{3, 1}}, {{1, 2}, {3, 5}}, {}, {}};
const auto distance = dijkstra(graph, 0);
for (std::size_t i = 0; i < distance.size(); ++i) {
if (i != 0) std::cout << ',';
if (distance[i] == INF) std::cout << "Infinity";
else std::cout << distance[i];
}
std::cout << '\n';
return 0;
}
0,3,1,4,Infinity
TypeScript