Cod sursa(job #2941127)

Utilizator Goia_DariusGoia Darius Goia_Darius Data 17 noiembrie 2022 10:21:27
Problema Distante Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>

using namespace std;
ifstream f("distante.in");
ofstream g("distante.out");
int T,n,m,sursa,a,b,c,k;
int costuri_calc[50010],Tati[3][250010],cost[50010],Start[50010],fr[50010],viz[50010],vec[1000010];
int Solve();
int main()
{
    f>>T;
    for(int TT=1;TT<=T;TT++)
    {
        f>>n>>m>>sursa;
        for(int nn=1;nn<=n;nn++)
            f>>costuri_calc[nn];
        for(int i=1;i<=m;i++)
        {
            f>>a>>b>>c;
            Tati[0][i]=b;
            Tati[1][i]=Start[a];
            Tati[2][i]=c;
            Start[a]=i;
        }
        for(int i=2;i<=n;i++)
            cost[i]=300000000;
        vec[1]=sursa;
        if(Solve()) g<<"DA"<<endl;
        else g<<"NU"<<endl;
    }
}
int Solve ()
{
    int pi=1,ps=1,st,elem;
    while(ps<=pi)
    {
        elem=vec[ps];
        viz[elem]=0;
        st=Start[elem];
        fr[elem]++;
        if(fr[elem]>=n)
        {
            return 0;
            break;
        }
        while(st)
        {
            if(cost[elem]+Tati[2][st]<cost[Tati[0][st]])
            {
                cost[Tati[0][st]]=cost[elem]+Tati[2][st];

                if(viz[Tati[0][st]]==0)
                {
                    viz[Tati[0][st]]=1;
                    vec[++pi]=Tati[0][st];

                }
            }
            st=Tati[1][st];
        }
        ps++;
    }
    for(int i=1;i<=n;i++)
        if(cost[i]!=costuri_calc[i])
            return 0;
    return 1;
}