Cod sursa(job #2254186)

Utilizator BiancaMariaVulsanVulsan Bianca Maria BiancaMariaVulsan Data 4 octombrie 2018 20:53:33
Problema Distante Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define nmax 50005
#define inf 1e9
using namespace std;
ifstream f("distante.in");
ofstream g("distante.out");
int n,m,s, nr, dist[nmax], d[nmax], viz[nmax];
vector < pair<int,int> > v[nmax];
priority_queue < pair<int,int> > q;

void dijkstra()
{
    int poz, nod, cost,i;
    for(i=1; i<=n; i++)
        {d[i]=inf; viz[i]=0;}
    d[s]=0;
    q.push({0,s});
    while(!q.empty())
    {
        poz=q.top().second;
        q.pop();
        if(!viz[poz])
        {
            viz[poz]=1;
            for(i=0; i<v[poz].size(); i++)
                {
                    nod=v[poz][i].first;
                    cost=v[poz][i].second;
                    if(d[nod]>d[poz]+cost)
                    {
                        d[nod]=d[poz]+cost;
                        q.push({-d[nod], nod});
                    }
                }
        }
    }
}

void citire()
{
    f>>nr;
    int i,j,c,k,ok;
    while(nr)
    {
        ok=1;
        f>>n>>m>>s;
        for(k=1; k<=n; k++)
            f>>dist[k];
        for(k=1; k<=m; k++)
        {
            f>>i>>j>>c;
            v[i].push_back({j,c});
            v[j].push_back({i,c});
        }
        dijkstra();
        for(i=1; i<=n; i++)
            if(dist[i]!=d[i])
                {ok=0; break;}
        if(ok) g<<"DA\n";
        else   g<<"NU\n";

        for(i=1; i<=n; i++)
            v[i].clear();

        nr--;
    }
}

int main()
{
    citire();
    f.close();
    g.close();
    return 0;
}