Cod sursa(job #2764951)

Utilizator DragosC1Ciobanu Dragos DragosC1 Data 23 iulie 2021 20:34:11
Problema Distante Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.64 kb
#include <fstream>
#include <queue>
#include <iostream>
#include <vector>
using namespace std;

ifstream f;
ofstream g;

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> Q;

vector<pair<int, int>> a[50001];
int dBronzarel[50001];
int dcorect[50001];

const int Inf = 1e9;

void dijkstra(int x) {
    int i;
    pair<int, int> p, cur;
    dcorect[x] = 0;
    Q.push({0, x});
    while (!Q.empty()) {
        p = Q.top();
        Q.pop();
        if (dcorect[p.second] != p.first) continue;
        for (i = 0; i < a[p.second].size(); i++) {
            cur = a[p.second][i];
            if (dcorect[cur.second] > dcorect[p.second] + cur.first) {
                dcorect[cur.second] = dcorect[p.second] + cur.first;
                Q.push({dcorect[cur.second], cur.second});
            }
        }
    }
}

void solve() {
    int i, n, m, sursa, x, y, cost;
    f >> n >> m >> sursa;
    for (i = 1; i <= n; i++) 
        f >> dBronzarel[i];
    for (i = 1; i <= m; i++) {
        f >> x >> y >> cost;
        a[x].push_back({cost, y});
        a[y].push_back({cost, x});
    }
    for (i = 1; i <= n; i++)
        dcorect[i] = Inf;
    dijkstra(sursa);
    bool ok = 1;
    for (i = 1; i <= n && ok; i++) 
        if (dcorect[i] != dBronzarel[i])
            ok = 0;
    if (ok == 1)
        g << "DA\n";
    else g << "NU\n";
    for (i = 1; i <= n; i++)
        a[i].clear();
}

void read() {
    int T;
    f.open("distante.in");
    g.open("distante.out");
    f >> T;
    while (T--)
        solve();
    g.close();
    f.close();
}

int main() {
    read();
    return 0;
}