Pagini recente » Borderou de evaluare (job #428286) | Cod sursa (job #1403848) | Diferente pentru utilizator/victor.ionescu intre reviziile 7 si 36 | Cod sursa (job #2274558) | Cod sursa (job #677185)
Cod sursa(job #677185)
#include <fstream>
#include <stdio.h>
using namespace std;
ofstream g("dijkstra.out");
FILE * stefi;
struct nod
{
long long inf,dis;
nod *urm;
};
nod *p[50003],*ultim[50003];
long long n,m,a,b,c,i,x;
long long viz[50003],l[50003];
void creare(nod *p[50003],nod *ultim[50003],long long n)
{
for (i=1;i<=n;i++)
{ p[i]=new nod;
p[i]->inf=0;
p[i]->urm=NULL;
ultim[i]=p[i];
}
}
void citire()
{
nod *q;
for (i=1;i<=m;i++)
{
fscanf(stefi,"%ld%ld%ld",&a,&b,&c);
q=new nod;
q->inf=b;
q->dis=c;
q->urm=NULL;
ultim[a]->urm=q;
ultim[a]=q;
}
}
void sterg()
{
nod *q;
for (i=1;i<=n;i++)
{
q=p[i];
p[i]=p[i]->urm;
q->urm=NULL;
delete q;
}
}
void dijkstra()
{
nod *q;
long long j,minim,maxim=999999999;
x=1;
viz[x]=1;
q=p[x];
while (q)
{
l[q->inf]=q->dis;
q=q->urm;
}
for (i=1;i<=n;i++)
if (i!=x && !l[i]) l[i]=maxim;
l[x]=0;
for (i=1;i<=n-1;i++)
{
for (j=1;j<=n;j++)
{
minim=maxim;
if (viz[j]==0 && l[j]<minim)
{
minim=l[j];
x=j;
}
}
viz[x]=1;
q=p[x];
while (q)
{
if (viz[j]==0 && l[q->inf]>l[x]+q->dis)
l[q->inf]=l[x]+q->dis;
q=q->urm;
}
}
}
int main()
{
stefi=fopen("dijkstra.in","r");
fscanf(stefi,"%ld%ld",&n,&m);
creare(p,ultim,n);
citire();
sterg();
dijkstra();
for (i=2;i<=n;i++)
g<<l[i]<<' ';
g.close();
return 0;
}