?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <fstream>
#include <vector>
 
int main(){
    std::ifstream fin("distante.in");
    std::ofstream fout("distante.out");
 
    short T; fin>>T;
    while(T--){
 
        unsigned n,m,s; fin>>n>>m>>s;
 
        std::vector<unsigned> dist(n+1);
        for(unsigned i=1;i<=n;++i) fin>>dist[i];
 
        std::vector<bool> verif(n+1,false);
        bool cont=true;
 
        if(dist[s]==0) verif[s]=true;
        else cont=false;
 
        for(unsigned i=0;i<m;++i){
            unsigned a,b; unsigned c; fin>>a>>b>>c;
 
            if(dist[b]>dist[a]+c) cont=false;
            else if(dist[b]==dist[a]+c) verif[b]=true;
 
            if(dist[a]>dist[b]+c) cont=false;
            else if(dist[a]==dist[b]+c) verif[a]=true;
 
        }
 
        for(unsigned i=1;i<=n&&cont;++i) if(!verif[i]) cont=false;
 
        if(cont) fout<<"DA\n";
        else fout<<"NU\n";
 
    }
}