Pagini recente » Cod sursa (job #2677409) | Cod sursa (job #177119) | Cod sursa (job #3675) | Cod sursa (job #1385497) | Cod sursa (job #2860305)
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <limits.h>
#define INF INT_MAX
#define NMax 50005
using namespace std;
ifstream fin ("dijkstra2.in");
ofstream fout("dijkstra2.out");
int N;
int Distanta[NMax];
vector < pair <int, int> > G[NMax];
struct Conditie
{
bool operator() (int x, int y)
{
return Distanta[x] > Distanta[y];
}
};
priority_queue <int, vector <int>, Conditie> Coada;
void Citire()
{
int M, A, B, C;
fin >> N >> M;
for(int i = 1; i <= M; ++ i)
{
fin >> A >> B >> C;
G[A].push_back( make_pair(B, C) );
}
}
void Dijkstra(int nodStart)
{
bool inCoada[NMax];
for(int i = 1; i <= N; ++ i)
Distanta[i] = INF;
Distanta[nodStart] = 0;
Coada.push(nodStart);
inCoada[nodStart] = true;
while( !Coada.empty() )
{
int nodCurent = Coada.top();
Coada.pop();
inCoada[nodCurent] = false;
for(unsigned int i = 0; i < G[nodCurent].size(); ++ i)
{
int Vecin = G[nodCurent][i].first;
int Cost = G[nodCurent][i].second;
if(Distanta[Vecin] > Distanta[nodCurent] + Cost)
{
Distanta[Vecin] = Distanta[nodCurent] + Cost;
if(inCoada[Vecin] == false)
{
Coada.push(Vecin);
inCoada[Vecin] = true;
}
}
}
}
}
void Afisare()
{
for(int i = 2; i <= N; ++ i)
{
if(Distanta[i] != INF)
fout << Distanta[i] << ' ';
else fout << 0 << ' ';
}
}
int main()
{
Citire();
Dijkstra(1);
Afisare();
return 0;
}