Cod sursa(job #284428)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 21 martie 2009 18:21:20
Problema Distante Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 1.32 kb
#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;

int main()
{
    int i,j,ok;    
    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]);
        for (i=1;i<=m;++i)
        {
            scanf("%d %d %d\n", &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=1;
        while(ok)
        {
            ok=0;
            for (i=1;i<=m;++i)
                  if (d[y[i]]>d[x[i]]+c[i])
                       d[y[i]]=d[x[i]]+c[i],
                       ok=1;
        }                         
        ok=1;
        for (i=1;i<=n;++i)
              if (d[i]!=d1[i])
                  {
                      ok=0;
                      break;
                  }
        if (ok==1)
             printf("DA\n");
             else
             printf("NU\n");
    }
    return 0;
}