Pagini recente » Borderou de evaluare (job #861053) | Borderou de evaluare (job #1859755) | Cod sursa (job #2176408)
#include <bits/stdc++.h>
using namespace std;
ifstream in("distante.in");
ofstream out("distante.out");
const int NMax = 50005;
const int inf = 1e9;
vector< vector< pair< int, int > > > G(NMax);
vector< int > distante(NMax, inf);
void dijkstra(int nodSursa) {
set< pair< int, int > > q;
distante[nodSursa] = 0;
q.insert(make_pair(0, nodSursa));
while(!q.empty()) {
int tempNode = q.begin()->second; q.erase(q.begin());
for(auto vecin: G[tempNode]) {
int len = vecin.second;
if(distante[tempNode] + len < distante[vecin.first]) {
q.erase(make_pair(distante[vecin.first], vecin.first));
distante[vecin.first] = distante[tempNode] + len;
q.insert(make_pair(distante[vecin.first], vecin.first));
}
}
}
}
int main() {
int T; in >> T;
while(T--) {
int n, m, nodSursa; in >> n >> m >> nodSursa;
distante.resize(n + 1, inf);
vector< int > distanteBronzorel(n + 1);
for(int i = 1; i <= n; ++i) {
in >> distanteBronzorel[i];
}
for(int i = 1; i <= m; ++i) {
int a, b, c; in >> a >> b >> c;
G[a].push_back(make_pair(b, c));
G[b].push_back(make_pair(a, c));
}
dijkstra(nodSursa);
bool ok = true;
for(int i = 1; i <= n && ok; ++i) {
ok = (distante[i] == distanteBronzorel[i]);
}
if(ok) {
out << "DA\n";
} else {
out << "NU\n";
}
for(int i = 1; i <= n; ++i) {
G[i].clear();
}
}
in.close(); out.close();
return 0;
}