# Cod sursa(job #2455568)

Utilizator Data 11 septembrie 2019 22:25:38 Distante 60 cpp-64 done Arhiva de probleme 1.64 kb
``````#include <iostream>
#include <queue>
#include <vector>

#define NMAX 50000
#define INFINIT 1000000000

using namespace std;

struct muchie {
int to ;
int cost ;
bool operator < (const muchie& a) const {
return this->cost > a.cost ;
}
};

int distgigel [ NMAX + 1 ] ;
vector<muchie> g [ NMAX + 1 ] ;
int mydist [ NMAX + 1 ] ;

bool dijkstra (int n, int sursa ) {
int i ;
for (i = 1 ; i <= n ; i++ )
mydist[i] = INFINIT ;
priority_queue<muchie> q ;
mydist[sursa] = 0 ;
for (auto elem : g[sursa] )
q.push({elem.to, elem.cost+mydist[sursa]}) ;
while (!q.empty()) {
if (mydist[q.top().to] == INFINIT ) {
int next = q.top().to ;
int val = q.top().cost ;
mydist[next] = val ;
if (mydist[next] != distgigel[next] )
return false ;
q.pop() ;
for (auto elem : g[next])
if (mydist[elem.to] == INFINIT )
q.push({elem.to, val+elem.cost}) ;
}
else
q.pop() ;
}
return true ;
}

int main() {
FILE *fin, *fout ;
fin = fopen ("distante.in", "r" ) ;
fout = fopen ("distante.out", "w" ) ;
int n, t, s, m, i, c, a, b ;
fscanf (fin, "%d", &t ) ;
while (t > 0 ) {
fscanf (fin, "%d%d%d", &n, &m, &s ) ;
for (i = 1 ; i <= n ; i++ )
fscanf (fin, "%d", &distgigel[i] ) ;
for (i = 1 ; i <= m ; i++ ) {
fscanf (fin, "%d%d%d", &a, &b, &c ) ;
g[a].push_back({b, c}) ;
g[b].push_back({a, c}) ;
}
if (dijkstra(n, s))
fprintf (fout, "DA\n" ) ;
else
fprintf (fout, "NU\n" ) ;
for (i = 1 ; i <= n ; i++ )
g[i].clear() ;
t--;
}
return 0;
}
``````