Pagini recente » Borderou de evaluare (job #1125666) | Cod sursa (job #2802109)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
const int nmax = 5005;
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));
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;
}