Pagini recente » Borderou de evaluare (job #77235) | Cod sursa (job #805308)
Cod sursa(job #805308)
#include<cstdio>
#define INF 0x3f3f3f3f
#define maxn 2005
#include<bitset>
using namespace std;
bitset <maxn> v;
short a[maxn][maxn],p[maxn];
int d[maxn],n,m,i,j,x,y,c,k,x0,mini,e_nod;
int main()
{
freopen("dijkstra.in","r",stdin);
freopen("dijkstra.out","w",stdout);
scanf("%d%d",&n,&m);
for(i=1;i<=n;++i)
for(j=1;j<=n;++j)
if(i!=j)
a[i][j]=INF;
for(;m>0;--m)
{
scanf("%d%d%d",&x,&y,&c);
a[x][y]=c;
}
x0=1;
for(i=1;i<=n;++i)
{
d[i]=a[x0][i];
if(d[i]!=INF)
p[i]=x0;
}
v[x0]=1; e_nod=1;
while(e_nod)
{
mini=INF;
for(i=1;i<=n;++i)
if(d[i]<mini&&v[i]==0)
mini=d[i],k=i;
if(mini!=INF)
{
v[k]=1;
for(i=1;i<=n;++i)
if(d[k]+a[k][i]<d[i])
{
d[i]=d[k]+a[k][i];
p[i]=k;
}
}
else
e_nod=0;
}
for(i=2;i<=n;++i)
if(d[i]!=INF)
printf("%d ",d[i]);
else
printf("0 ");
printf("\n");
return 0;
}