Pagini recente » Cod sursa (job #3127969) | Cod sursa (job #1194520) | Cod sursa (job #2884760) | Cod sursa (job #2643539) | Cod sursa (job #2949262)
#include <bits/stdc++.h>
#define int long long
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int n, m, i, nr1, nr2, nr3;
pair <int, int> aici;
int32_t main()
{
const int maxx = 2147483647;
fin >> n >> m;
vector <vector <pair <int, int>>> adjl(n+1);
for (i = 0; i < m; ++i){
fin >> nr1 >> nr2 >> nr3;
adjl[nr1].push_back({nr2, nr3});
}
fin.close();
vector <int> viz(n+1), dist(n+1, maxx);
priority_queue <pair <int, int>, vector <pair<int, int>>, greater <pair <int, int>>> hip;
hip.push({0, 1});
dist[1] = 0;
while (!hip.empty()){
aici = hip.top();
hip.pop();
if (viz[aici.second])
continue;
for (auto & r : adjl[aici.second]){
if (dist[r.first] > r.second + dist[aici.second]){
dist[r.first] = r.second + dist[aici.second];
hip.push({dist[r.first], r.first});
}
}
viz[aici.second] = 1;
}
for (i = 2; i <= n; ++i){
if (dist[i] != maxx)
fout << dist[i] << ' ';
else
fout << 0 << ' ';
}
fout << '\n';
fout.close();
return 0;
}