Pagini recente » Rezultatele filtrării | Rezultatele filtrării | Rezultatele filtrării | Borderou de evaluare (job #181461) | Cod sursa (job #2380609)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
#define nmax 50005
#define INF 1000000
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int n,m,i,j,p,a,b,c,nod_crt,vecin,cost;
int Dist[nmax];
bool in_coada[nmax];
struct compara
{
bool operator()(int x, int y)
{
return Dist[x]>Dist[y];
}
};
vector < pair<int,int> > v[nmax];
priority_queue <int, vector<int>, compara> coada;
void Dijkstra(int start)
{
for(int i=1;i<=n;i++)
Dist[i]=INF;
Dist[start]=0;
coada.push(start);
in_coada[start]=true;
while(!coada.empty())
{
nod_crt=coada.top();
coada.pop();
in_coada[nod_crt]=false;
for(int i=0;i<v[nod_crt].size();i++)
{
vecin=v[nod_crt][i].first;
cost=v[nod_crt][i].second;
if(Dist[nod_crt]+cost<Dist[vecin])
{
Dist[vecin]=Dist[nod_crt]+cost;
if(in_coada[vecin]==false)
{
coada.push(vecin);
in_coada[vecin]=true;
}
}
}
}
}
int main()
{
fin>>n>>m;
for(int i=1;i<=m;i++)
{
fin>>a>>b>>c;
v[a].push_back(make_pair(b,c));
}
Dijkstra(1);
for(int i=2;i<=n;i++)
{
if(Dist[i]==INF)
fout<<0<<" ";
else
fout<<Dist[i]<<" ";
}
}