Pagini recente » Borderou de evaluare (job #2479740) | Cod sursa (job #1837787) | Cod sursa (job #2049733)
/**vector d( cu dist minime) in care toate inafara de primu is infinit oo=constanta mare aproape de infinit
luam minimu din d si ii relaxam vecinii (daca distanta panal la el + d[don curent]ii mai mica decat d[nodul resp le bagam])
vector bool s cu in care nod am mai fost sa nu repetam
pair <int,int>P[100];
P=makepair(1,2);
cout<<P.first<<P.second;*/
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
const int NMax=50000;
const int oo=2000000000;
int D[NMax+5],S[NMax+5],n,m,i,x,y,z,Nod;
vector <pair<int,int> > G[NMax+5];
void citire()
{
in>>n>>m;
for(int i=1;i<=m;++i)
{
in>>x>>y>>z;
G[x].push_back(make_pair(y,z));
}
}
void dijkstra()
{
for(int i=2;i<=n;++i)
D[i]=oo;
for(int k=1;k<=n;++k)
{
int Min=oo;
for(int i=1;i<=n;++i)
if(D[i]<Min && S[i]==0)
{
Min=D[i];
Nod=i;
}
S[Nod]=1;
for(int i=0;i< (int)G[Nod].size();++i)
{
int Vecin=G[Nod][i].first;
int Cost=G[Nod][i].second;
D[Vecin]=min(D[Vecin],D[Nod]+Cost);
}
}
}
void afisare()
{
for(i=2;i<=n;++i)
out<<D[i]<<" ";
}
int main()
{
citire();
dijkstra();
afisare();
}