From 96254947699986c59f0dc63d69fd4b76bd3ed43e Mon Sep 17 00:00:00 2001
From: Sebastiano Tronto <sebastiano@tronto.net>
Date: Mon, 6 Jul 2026 19:08:08 +0200
Subject: Initial commit

---
 04_graph_algorithms/shortest_routes_i_1671.cpp | 43 ++++++++++++++++++++++++++
 1 file changed, 43 insertions(+)
 create mode 100644 04_graph_algorithms/shortest_routes_i_1671.cpp

(limited to '04_graph_algorithms/shortest_routes_i_1671.cpp')

diff --git a/04_graph_algorithms/shortest_routes_i_1671.cpp b/04_graph_algorithms/shortest_routes_i_1671.cpp
new file mode 100644
index 0000000..89f675d
--- /dev/null
+++ b/04_graph_algorithms/shortest_routes_i_1671.cpp
@@ -0,0 +1,43 @@
+#include <iostream>
+#include <queue>
+#include <utility>
+#include <vector>
+
+class dvpair {
+public:
+	size_t d;
+	size_t v;
+	auto operator<=>(const dvpair& p) const { return p.d <=> d; }
+};
+
+int main() {
+	size_t n, m;
+	std::cin >> n >> m;
+	std::vector<std::vector<std::pair<size_t, size_t>>> a(n);
+	for (size_t i = 0; i < m; i++) {
+		size_t x, y, z;
+		std::cin >> x >> y >> z;
+		a[x-1].push_back({y-1, z});
+	}
+
+	constexpr size_t inf{999999999999999ULL};
+	std::vector<size_t> d(n, inf);
+	std::priority_queue<dvpair> q;
+	d[0] = 0;
+	q.push({0, 0});
+	while (!q.empty()) {
+		auto [dd, p] = q.top();
+		q.pop();
+		if (dd > d[p])
+			continue;
+		for (auto [r, w] : a[p]) {
+			if (w + d[p] < d[r]) {
+				d[r] = d[p] + w;
+				q.push({d[r], r});
+			}
+		}
+	}
+	for (auto x : d)
+		std::cout << x << " ";
+	std::cout << "\n";
+}
-- 
cgit v1.3