Pagini recente » Cod sursa (job #2409657) | Cod sursa (job #2409644) | Cod sursa (job #64437) | Cod sursa (job #2409654)
#include <bits/stdc++.h>
using namespace std;
const int DIM = 50005;
const int INF = 2000000005;
int dp[DIM];
vector<pair<int, int> > edg[DIM];
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > prq;
int main(void)
{
freopen("dijkstra.in", "r", stdin);
freopen("dijkstra.out", "w", stdout);
int n, m; cin >> n >> m;
for (int i = 1; i <= m; ++i) {
int x, y, c; cin >> x >> y >> c;
edg[x].push_back(make_pair(y, c)); }
for (int i = 2; i <= n; ++i) {
dp[i] = INF; }
prq.push(make_pair(0, 1));
while (prq.size()) {
int d = prq.top().first,
x = prq.top().second;
prq.pop();
if (d > dp[x]) {
continue; }
for (pair<int, int> it : edg[x]) {
int y = it.first, c = it.second;
if (dp[y] > dp[x] + c) {
dp[y] = dp[x] + c;
prq.push(make_pair(dp[y], y)); } } }
for (int i = 2; i <= n; ++i) {
if (dp[i] == INF) {
dp[i] = 0; }
cout << dp[i] << " "; }
return 0;
}