Pagini recente » Cod sursa (job #2562841) | Cod sursa (job #2717647)
#include <bits/stdc++.h>
#include <cassert>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<double, double>;
using pld = pair<ld, ld>;
int main()
{
ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");
int N, M;
cin >> N >> M;
vector<vector<pi>> adj(N + 1);
while (M--)
{
int x, y, weight;
cin >> x >> y >> weight;
adj[x].emplace_back(y, weight);
adj[y].emplace_back(x, weight);
}
vector<int> shortest_dist(N + 1, 2e9);
auto Dijkstra = [&](const int start_node) -> void
{
priority_queue<pi, vector<pi>, greater<pi>> nodes;
nodes.emplace(0, start_node);
shortest_dist[start_node] = 0;
while (!nodes.empty())
{
const int cur_node = nodes.top().second, dist_from_start_node = nodes.top().first;
nodes.pop();
if (dist_from_start_node != shortest_dist[cur_node])
{
continue;
}
for (const auto &_adj_node : adj[cur_node])
{
const int adj_node = _adj_node.first, weight = _adj_node.second;
if (dist_from_start_node + weight < shortest_dist[adj_node])
{
nodes.emplace(shortest_dist[adj_node] = dist_from_start_node + weight, adj_node);
}
}
}
};
Dijkstra(1);
for (int node = 2; node <= N; ++node)
{
cout << shortest_dist[node] << " ";
}
}