# Cod sursa(job #2764951)

Utilizator Data 23 iulie 2021 20:34:11 Distante 100 cpp-64 done Arhiva de probleme 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();
}

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

int main() {