Cod sursa(job #1338825)

Utilizator Corina1997Todoran Ana-Corina Corina1997 Data 10 februarie 2015 13:33:34
Problema Distante Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <fstream>
using namespace std;

ifstream is("distante.in");
ofstream os("distante.out");

int t, n, s, m, a[50001], d[50001];
int x, y, cost;
bool ok;

int main()
{
    is >> t;
    for( int i = 1; i <= t; i++ )
    {
        is >> n >> m >> s;
        ok = true;
        for ( int i = 1; i <= n; i++ )
            is >> a[i];
        for ( int i = 1; i <= m; i++ )
        {
            is >> x >> y >> cost;
            if ( a[x] + cost < a[y] || a[y] + cost < a[x] )
                ok = false;
            if ( a[x] + cost == a[y] )
                d[y] = 1;
            if ( a[y] + cost == a[x] )
                d[x] = 1;
        }
        if ( d[s] == 1 )
            ok = false;
        for ( int i = 1; i <= n; i++ )
            if ( d[i] == 0 && i != s )
                ok = false;
        if ( ok )
            os << "DA\n";
        else
            os << "NU\n";
    }
    is.close();
    os.close();
    return 0;
}