# Cod sursa(job #279653)

Utilizator Data 12 martie 2009 21:52:17 Distante 0 cpp done Arhiva de probleme 1.11 kb
``````#include <stdio.h>
#define nmax 50005
#define inf 2000000000
struct graf
{
long vi,vf,cost;
}q[100005];
long d[nmax],n,m,dd[nmax];

void ford(long s)
{
int p=1;
long i,j,a,b,c;
for (i=1;i<=n;i++)
if (i!=s) d[i]=inf;
d[s]=0;
i=1;
while (i<n&&p)
{
p=0;
for (j=1;j<=m;j++)
{
a=q[j].vi;
b=q[j].vf;
c=q[j].cost;
if (d[b]>d[a]+c)
{
d[b]=d[a]+c;
p=1;
}
a=q[i].vf;
b=q[j].vi;
if (d[b]>d[a]+c)
{
d[b]=d[a]+c;
p=1;
}
}
}
}

int main()
{
long t,i,pp,x,y,z;
long s,j;
freopen("distante.in","r",stdin);
freopen("distante.out","w",stdout);
scanf("%ld",&t);
for (i=1;i<=t;i++)
{
scanf("%ld%ld%ld",&n,&m,&s);
pp=1;
for (j=1;j<=n;j++)
scanf("%ld",&dd[j]);
for (j=1;j<=m;j++)
{
scanf("%ld%ld%ld",&x,&y,&z);
q[j].vi=x;
q[j].vf=y;
q[j].cost=z;
/*
q[j+1].vi=y;
q[j+1].vf=x;
q[j+1].cost=z;
*/
}

ford(s);

for (j=1;j<=n;j++)
{
if (d[j]==inf) d[j]=0;
if (dd[j]!=d[j]) pp=0;
}
if (pp) printf("DA\n");
else printf("NU\n");
}

return 0;
}``````