shortest_routes_i_1671.cpp (807B)
1 #include <iostream> 2 #include <queue> 3 #include <utility> 4 #include <vector> 5 6 class dvpair { 7 public: 8 size_t d; 9 size_t v; 10 auto operator<=>(const dvpair& p) const { return p.d <=> d; } 11 }; 12 13 int main() { 14 size_t n, m; 15 std::cin >> n >> m; 16 std::vector<std::vector<std::pair<size_t, size_t>>> a(n); 17 for (size_t i = 0; i < m; i++) { 18 size_t x, y, z; 19 std::cin >> x >> y >> z; 20 a[x-1].push_back({y-1, z}); 21 } 22 23 constexpr size_t inf{999999999999999ULL}; 24 std::vector<size_t> d(n, inf); 25 std::priority_queue<dvpair> q; 26 d[0] = 0; 27 q.push({0, 0}); 28 while (!q.empty()) { 29 auto [dd, p] = q.top(); 30 q.pop(); 31 if (dd > d[p]) 32 continue; 33 for (auto [r, w] : a[p]) { 34 if (w + d[p] < d[r]) { 35 d[r] = d[p] + w; 36 q.push({d[r], r}); 37 } 38 } 39 } 40 for (auto x : d) 41 std::cout << x << " "; 42 std::cout << "\n"; 43 }