Cod sursa(job #284518)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 21 martie 2009 19:00:11
Problema Distante Scor 50
Compilator c Status done
Runda Arhiva de probleme Marime 1.79 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;
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;
}