Cod sursa(job #2830457)

Utilizator petru.burdusaBurdusa Petru petru.burdusa Data 9 ianuarie 2022 22:09:44
Problema Distante Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.82 kb
#include<fstream>
#include<iostream>
#include<set>
#include<vector>
#include <queue>
using namespace std;
int estimare[50005],src,t,n,m,i,j,viz[50005],r[50005],q,a,b,minim,contor,x,y,z,w;


int main()
{
    ifstream in("distante.in");
    ofstream out("distante.out");
    in>>t;
    for(int idx = 0; idx < t; idx++)
    {
        vector <int> v[50005],d[50005];
        in>>n>>m>>src;
        priority_queue < pair<int,int>, vector < pair<int,int> >, greater < pair<int,int> > > s;
        contor = 0;
        for(i=1;i<=n;i++)
        {
            in>>estimare[i];
            r[i]=1<<30;
            viz[i]=0;


        }
        r[src]=0;
        for(i=1;i<=m;i++)
        {
            in>>x>>y>>z;
            v[x].push_back(y);
            d[x].push_back(z);
            v[y].push_back(x);
            d[y].push_back(z);
        }
        s.push(make_pair(0,src));
        contor++;
        while(contor>0)
        {
            w=s.top().first;
            q=s.top().second;
            if(viz[q]==1)
            {
                s.pop();
                contor--;
            }
            else
            {
                viz[q]=1;
                minim=1<<30;
                for(i=0;i<v[q].size();i++)
                {
                    if(r[v[q][i]]>r[q]+d[q][i])
                    {

                        r[v[q][i]]=r[q]+d[q][i];
                        s.push(make_pair(r[v[q][i]],v[q][i]));
                        contor++;

                    }

                }
            }

        }
        bool ok = 1;
        for(i=1;i<=n;i++)
        {
            if(r[i] != estimare[i])
                ok=0;
            /*if(r[i]==1<<30)
                cout<<r[i]<<' ';
            else
                cout<<r[i]<<' ';*/
        }
        if(ok==0)
            out<<"NU";
        else
            out<<"DA";
        out<<'\n';
    }


}