Cod sursa(job #2178457)

Utilizator emiliancsEmilian Stavarache emiliancs Data 19 martie 2018 14:51:07
Problema Distante Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
#include<cstdio>
#include<cstring>
using namespace std;
int d[50005],ok[50005];
int main(){
freopen("distante.in","r",stdin);
freopen("distante.out","w",stdout);
int t,i1,n,m,a,b,c,i,s;
scanf("%d",&t);
for(i1=1;i1<=t;i1++){
scanf("%d%d%d",&n,&m,&s);
for(i=1;i<=n;i++)
scanf("%d",&d[i]);
if (d[s]!=0){
printf("NU\n");
continue;}
memset(ok,0,sizeof(ok));
for(i=1;i<=m;i++){
scanf("%d%d%d",&a,&b,&c);
if (d[a]+c<d[b] || d[b]+c<d[a]){
printf("NU\n");
for(i=i+1;i<=m;i++)
scanf("%d%d%d",&a,&b,&c);
i=m+3;
continue;}
if (d[a]+c==d[b] && a!=b)
ok[b]=1;
if (d[b]+c==d[a] && a!=b)
ok[a]=1;}
if (i==m+4)
continue;
ok[s]=1;
for(i=1;i<=n;i++)
if (ok[i]==0){
printf("NU\n");
i=n+3;
break;}
if (i==n+1)
printf("DA\n");}
return 0;}