Cod sursa(job #284518)
#include <stdio.h>
#include <string.h>
#define Nmax 50001
#define Inf 0x3f3f3f3f
int d[Nmax],d1[Nmax];
int x[2*Nmax],y[2*Nmax],c[2*Nmax];
int n,m,nod,T;
char ch[200];
int main()
{
int i,j,ok,xx,yy,zz;
freopen("distante.in","r",stdin);
freopen("distante.out","w",stdout);
scanf("%d\n", &T);
while(T--)
{
scanf("%d %d %d\n", &n,&m,&nod);
memset(d,0,sizeof(d));
for (i=1;i<=n;++i)
scanf("%d", &d1[i]);
scanf("\n");
for (i=1;i<=m;++i)
{
gets(ch);
xx=yy=zz=j=0;
while (ch[j]!=' '){xx=xx*10+ch[j]-'0';j++;}j++;
while (ch[j]!=' '){yy=yy*10+ch[j]-'0';j++;}j++;
while (ch[j]){zz=zz*10+ch[j]-'0';j++;}
x[i]=xx;
y[i]=yy;
c[i]=zz;
//scanf("%d %d %d", &x[i],&y[i],&c[i]);
if (x[i]==nod)
d[y[i]]=c[i];
}
for (i=1;i<=n;++i)
if (d[i]==0)
d[i]=Inf;
d[nod]=0;
ok=0;
while(!ok)
{
ok=1;
for (i=1;i<=m;++i)
if (d[y[i]]>d[x[i]]+c[i])
d[y[i]]=d[x[i]]+c[i],
ok=0;
else
if (d[x[i]]>d[y[i]]+c[i])
d[x[i]]=d[y[i]]+c[i],
ok=0;
}
for (i=1;i<=n;++i)
if (d[i]!=d1[i])
{
ok=0;
break;
}
if (ok)
printf("DA\n");
else
printf("NU\n");
}
return 0;
}