Cod sursa(job #2527362)

Utilizator matei123Biciusca Matei matei123 Data 20 ianuarie 2020 10:37:37
Problema Distante Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("distante.in"); ofstream g("distante.out");
const int INF=1e9+1;
int t,viz[50001],n,m,x,y,dist[50001],z,start,d[50001];
vector < pair<int,long int> > edge[50001];
struct cmp
{   bool operator ()(int x,int y)
    {   if(dist[x]>dist[y]) return 1;
        else return 0;
    }
};
priority_queue<int, vector<int>, cmp > q;
void dijkstra(int start)
{   q.push(start);
    dist[start]=0;
    viz[start]=1;
    while (!q.empty())
    {   int vert=q.top();
        q.pop();
        viz[vert]=0;
        for(int i=0;i<edge[vert].size();i++)
        {   int near=edge[vert][i].first;
            int cost=edge[vert][i].second;
            if(dist[near]>dist[vert]+cost)
            {   dist[near]=dist[vert]+cost;
                if(!viz[near])
                {   viz[near]=1;
                    q.push(near);
                }
            }
        }
    }
}
int main()
{   f>>t;
    for(int xd=1;xd<=t;xd++)
    {   f>>n>>m>>start;
        for(int i=1;i<=n;i++)
        {   dist[i]=INF;
            viz[i]=0;
            edge[i].clear();
        }
        for(int i=1;i<=n;i++) f>>d[i];
        for(int i=1;i<=m;i++)
        {   cin>>x>>y>>z;
            edge[x].push_back(make_pair(y,z));
            edge[y].push_back(make_pair(x,z));
        }
        dijkstra(start);
        d[start]=0;
        bool ok=true;
        for(int i=1;i<=n && ok;i++)
            if(d[i]!=dist[i]) ok=0;
        if(ok==true) g<<"DA"<<'\n';
        else g<<"NU"<<'\n';
    }
    g.close(); return 0;
}