Cod sursa(job #996459)

Utilizator horatiu11Ilie Ovidiu Horatiu horatiu11 Data 11 septembrie 2013 22:54:50
Problema Distante Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
# include <cstdio>
# define inf 2000000000
using namespace std;
int t,q,a[50001],D[50001],i,s,n,m,x,y,c;
struct muchie{int x,y,c;}G[100001];
bool ok;
int main()
{
    freopen("distante.in","r",stdin);
    freopen("distante.out","w",stdout);
    scanf("%d",&t);
    for(q=1;q<=t;++q)
    {
        scanf("%d%d%d",&n,&m,&s);
        for(i=1;i<=n;++i)
            scanf("%d",&a[i]);
        for(i=1;i<=m;++i)
        {
            scanf("%d%d%d",&x,&y,&c);
            G[i].x=x;G[i].y=y;G[i].c=c;
            if(x==s)
                D[y]=c;
            else if(y==s)
                D[x]=c;
        }
        do
        {
            ok=true;
            for(i=1;i<=m;++i)
            {
                if(D[G[i].y]>D[G[i].x]+G[i].c)
                {
                    D[G[i].y]=D[G[i].x]+G[i].c;
                    ok=false;
                }
                if(D[G[i].x]>D[G[i].y]+G[i].c)
                {
                    D[G[i].y]=D[G[i].x]+G[i].c;
                    ok=false;
                }
            }
        }while(!ok);
        ok=1;
        for(i=1;i<=n && ok;++i)
            if(a[i]!=D[i])ok=0;
        if(ok)printf("DA\n");
        else printf("NU\n");
    }
    return 0;
}