Pagini recente » Istoria paginii runda/26_februarie_simulare_oji_2024_clasa_10 | Cod sursa (job #2802107)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
const int nmax = 5005;
int extractMin(unordered_set<int> s, int* dMin, int N){
int mini = INT_MAX;
int poz = - 1;
for(int i = 1; i <= N; ++i)
if(s.find(i) == s.end() && dMin[i] < mini){
mini = dMin[i];
poz = i;
}
return poz;
}
int extractMin(priority_queue<pair<int, int>>& pq){
int temp = pq.top().second;
pq.pop();
return temp;
}
int main()
{ int N, M;
vector <pair<int, int>> adj[nmax];
priority_queue<pair<int, int>> pq; /// tine perechi de tip (cost, nod)
int dMin[nmax];
fin >> N >> M;
for(int k = 0; k < M; ++k){
int i, j, cost;
fin >> i >> j >> cost;
adj[i].push_back(make_pair(j, cost));
}
dMin[1] = 0;
for(int i = 2; i <= N; ++i)
dMin[i] = INT_MAX / 2;
pq.push(make_pair(0, 1));
int crt = extractMin(s, dMin, N);
while(!(pq.empty())){
int crt = extractMin(pq);
for(auto vecin: adj[crt]){
int nnod = vecin.first;
int ccost = vecin.second;
if(ccost + dMin[crt] < dMin[nnod])
dMin[nnod] = ccost + dMin[crt];
pq.push(make_pair(dMin[nnod], nnod));
}
}
for(int i = 2; i <= N; ++i)
if(dMin[i] != INT_MAX / 2)
fout << dMin[i] << ' ';
else fout << 0 << ' ';
return 0;
}