Pagini recente » Borderou de evaluare (job #1446771) | Cod sursa (job #2741353)
#include <iostream>
#include <cstring>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
#define infi (1<<30)
#define f first
#define s second
vector <pair<int, int>> v[50002];
priority_queue< pair< int,int >, vector< pair< int, int >>, greater< pair< int, int >> >q;
int n, m, i, x, y, dp[50002], z, viz[50002], p, le;
void DIJ(){
int nc;
q.push({0,1});
while(q.size() ){
nc = q.top().s;
q.pop();
if (viz[nc] == 0)
{
viz[nc] = 1;
for (auto x : v[nc]) {
if (viz[x.s] == 0) {
if(dp[nc] + x.f < dp[x.s])
dp[x.s] = dp[nc] + x.f;
q.push({dp[nc] + x.f, x.s});
}
}
}
}
}
int main()
{
fin>>n>>m;
for(i = 1; i <= m; i++){
fin>>x>>y>>z;
v[x].push_back({z, y});
}
for (i = 2; i <= n; i++)
dp[i] = infi;
DIJ();
for(i = 2; i <= n; i++){
if ( dp[i] == infi )
fout<<0<<' ';
else
fout<<dp[i]<<' ';
}
return 0;
}