Cod sursa(job #515973)
#include <stdio.h>
const int maxn=50005, INF=5000000000LL;
int i,j,T,N,M,S,hp;
int H[maxn],poz[maxn];
long D[maxn],DB[maxn];
struct nod {
int inf,c;
nod *next;
} *A[maxn];
void add(int a, int b, int cst)
{
nod *q=new nod;
q->c=cst;
q->inf=b;
q->next=A[a];
A[a]=q;
}
void citire()
{
int a,b,cst;
scanf("%d %d %d",&N,&M,&S);
for(j=1;j<=N;j++) scanf("%d",&DB[j]);
for(j=1;j<=M;j++)
{
scanf("%d %d %d",&a,&b,&cst);
add(a,b,cst); add(b,a,cst);
}
}
void swap(int &a, int &b)
{
int aux=a;
a=b;
b=aux;
}
void upheap(int k)
{
while(D[H[k]]<D[H[k/2]] & k>1)
{
swap(H[k],H[k/2]);
swap(poz[H[k]],poz[H[k/2]]);
k=k/2;
}
}
void downheap(int k)
{
int son;
do
{
son=0;
if(2*k<=hp)
{
son=2*k;
if(son+1<=hp && D[H[son+1]]<D[H[son]])
son++;
if(D[H[son]]>D[H[k]])
son=0;
}
if(son)
{
swap(H[k],H[son]);
swap(poz[H[k]],poz[H[son]]);
k=son;
}
}
while(son);
}
void insert(int k)
{
H[++hp]=k;
poz[k]=hp;
upheap(hp);
}
int radacina()
{
int r=H[1];
swap(H[1],H[hp]);
swap(poz[H[1]],poz[H[hp]]);
hp--;
downheap(1);
return r;
}
void dijk(int k)
{
for(j=1;j<=N;j++) { D[j]=INF; H[j]=0; poz[j]=0; }
insert(k);
D[k]=0;
while(hp)
{
int x=radacina();
for(nod *q=A[x];q;q=q->next)
if(D[x]+q->c<D[q->inf])
{
D[q->inf]=D[x]+q->c;
if(poz[q->inf]==0)
insert(q->inf);
else
if(poz[q->inf]<=hp)
upheap(poz[q->inf]);
}
poz[x]=maxn+10;
}
}
int verif()
{
for(j=1;j<=N;j++)
if(DB[j]!=D[j]) return 0;
return 1;
}
int main()
{
freopen("distante.in","r",stdin);
freopen("distante.out","w",stdout);
scanf("%d",&T);
for(i=1;i<=T;i++)
{
citire();
dijk(S);
if(verif()) printf("DA\n");
else printf("NU\n");
}
}