Pagini recente » Cod sursa (job #27137) | Cod sursa (job #738020) | Cod sursa (job #1306047) | Cod sursa (job #1597824) | Cod sursa (job #794712)
Cod sursa(job #794712)
#include <vector>
#include <fstream>
#include <queue>
using namespace std;
#define INFILE "distante.in"
#define OUTFILE "distante.out"
#define pb push_back
#define pii pair<int,int>
#define NMAX 50010
#define inf 50000000
vector< vector< pii > > e;
int n, dist[NMAX], d[NMAX];
void bellman_ford(int start) {
for(int i=0; i<n; i++)
dist[i] = inf;
dist[start] = 0;
bool changed = true;
for(int i=0; i<n-1 && changed; i++)
{
changed = 0;
for(int j=0; j<n; j++)
for(vector<pii >::iterator it = e[j].begin(); it!=e[j].end(); it++)
if( dist[j] + it->first < dist[ it->second ] )
dist[ it->second ] = dist[j] + it->first, changed = 1;
}
}
int main() {
ifstream fin(INFILE);
ofstream fout(OUTFILE);
int cases;
fin >> cases;
for(;cases; cases--) {
int m, start;
fin >> n >> m >> start;
for(int i=0; i<n; i++)
fin >> d[i];
e.clear();
e.resize(n);
for(; m; m--) {
int a, b, c;
fin >> a >> b >> c;
e[a-1].pb(make_pair(c, b-1));
e[b-1].pb(make_pair(c, a-1));
}
bellman_ford(start-1);
bool ok = true;
for(int i=0; i<n && ok; i++)
if( dist[i]!=d[i] )
ok = false;
fout << (ok ? "DA" : "NU");
if( cases>1 ) fout << "\n";
}
return 0;
}