Cod sursa(job #2941265)

Utilizator andreipirjol5Andrei Pirjol andreipirjol5 Data 17 noiembrie 2022 15:24:38
Problema Distante Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.13 kb
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;
FILE *fin, *fout;

struct edge
{
    int dest, cost;
};

#define NMAX 50000
int d_given[NMAX + 5], d[NMAX + 5];

vector <edge> graph[NMAX + 5];

struct cmp
{
    bool operator()(edge e1, edge e2)
    {
        return (e1.cost > e2.cost) ? true : false;
    }
};

priority_queue <edge, vector <edge>, cmp> pq;

void dij(int node)
{
    edge e;
    e.dest = node;
    e.cost = 0;
    pq.push(e);

    while(!pq.empty())
    {
        e = pq.top();
        pq.pop();

        if(e.cost > d[e.dest])
            continue;

        for(auto neigh : graph[e.dest])
        {
            if(d[neigh.dest] == -1 or d[neigh.dest] > d[e.dest] + neigh.cost)
            {
                d[neigh.dest] = d[e.dest] + neigh.cost;

                edge new_edge;
                new_edge.dest = neigh.dest;
                new_edge.cost = d[neigh.dest];

                pq.push(new_edge);
            }
        }
    }
}

int main()
{
    fin = fopen("distante.in", "r");
    fout = fopen("distante.out", "w");

    int t;
    fscanf(fin, "%d", &t);

    int n, m, s;

    while(t--)
    {
        fscanf(fin, "%d%d%d", &n, &m, &s);

        int i;
        for(i = 1; i <= n; i++)
            fscanf(fin, "%d", &d_given[i]);

        edge e;
        int u, v, c;

        for(i = 1; i <= m; i++)
        {
            fscanf(fin, "%d%d%d", &u, &v, &c);

            e.dest = v;
            e.cost = c;

            graph[u].push_back(e);

            e.dest = u;

            graph[v].push_back(e);
        }

        for(i = 1; i <= n; i++)
            d[i] = -1;

        d[s] = 0;
        dij(s);

        bool ok = 1;


        for(i = 1; i <= n; i++)
            if(d[i] != d_given[i])
            {
                ok = 0;
                break;
            }

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

        if(ok == 1)
            fprintf(fout, "DA\n");
        else fprintf(fout, "NU\n");
    }

    fclose(fin);
    fclose(fout);
    return 0;
}