Cod sursa(job #383127)
#include <cstdio>
#include <vector>
#define NMAX 55001
#define POS 90001
#define INF 1000000000
using namespace std;
void initializare();
void citire();
void rezolvare();
void scrie();
int T;
int C[POS];
int N,M,INC;
vector<int> G[NMAX],H[NMAX];
int COADA[POS],NR=0;
int VAL[POS];
bool bou=0;
int main()
{
freopen("distante.in","r",stdin);
freopen("distante.out","w",stdout);
scanf("%d",&T);
for(int i=1;i<=T;i++)
{
initializare();
citire();
rezolvare();
scrie();
}
return 0;
}
void initializare()
{
for(int i=1;i<=NMAX;i++)
VAL[i]=INF;
}
void citire()
{
int x,y,v;
scanf("%d %d %d",&N,&M,&INC);
VAL[INC]=0;
for(int i=1;i<=N;i++)
scanf("%d",&C[i]);
for(int i=1;i<=M;i++)
{
scanf("%d %d %d",&x,&y,&v);
G[x].push_back(y);
H[x].push_back(v);
}
}
void rezolvare()
{
vector<int>::iterator it,ih;
for( it=G[INC].begin(), ih=H[INC].begin(); it!=G[INC].end() ;it++,ih++)
{
COADA[++NR]=*it;
VAL[COADA[NR]]=*ih;
}
for(int i=1;i<=NR;i++)
for( it=G[COADA[i]].begin(), ih=H[COADA[i]].begin(); it!=G[COADA[i]].end() ;it++,ih++)
if(*ih+VAL[COADA[i]]<VAL[*it])
{
COADA[++NR]=*it;
VAL[COADA[NR]]=*ih+VAL[COADA[i]];
}
}
void scrie()
{
for(int i=2;i<=N;i++)
if(VAL[i]!=C[i])
{
printf("NU\n");
return;
}
printf("DA\n");
}