# Cod sursa(job #2455548)

Utilizator Data 11 septembrie 2019 21:43:49 Distante 60 cpp-64 done Arhiva de probleme 1.9 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 ;
}
};

inline void dijkstra (int n, int sursa, int mydist [ NMAX + 1 ], vector<muchie> g [ NMAX + 1 ]) {
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 ;
q.pop() ;
for (auto elem : g[next])
if (mydist[elem.to] == INFINIT )
q.push({elem.to, val+elem.cost}) ;
}
else
q.pop() ;
}
}

inline bool verif_dijkstra (int n, int sursa, int distgigel[ NMAX + 1 ], vector<muchie> g [ NMAX + 1 ] ) {
int i ;
int mydist [ NMAX + 1 ] ;
for (i = 1 ; i <= n ; i++ )
mydist[i] = INFINIT ;
dijkstra(n, sursa, mydist, g) ;
i = 1 ;
while (i <= n && mydist[i] == distgigel[i] )
i++;
if (i > n )
return true ;
return false ;
}

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