Pagini recente » Borderou de evaluare (job #2385502) | Cod sursa (job #516032)
Cod sursa(job #516032)
#include<fstream>
#include<vector>
#include<queue>
using namespace std;
ifstream f("distante.in");
ofstream g("distante.out");
#define nmax 50002
typedef struct noduri{int vec,dist;};
noduri aux;
vector <noduri> v[nmax];
queue <int> Q;
int n,m,t,S,d[nmax],l[nmax],Sursa;
bool inQ[nmax];
void afisare()
{
int i;bool bla;
if(d[Sursa])
{
g<<"NU"<<'\n'; return;
}
for(S=1;S<=n;S++)
if(S!=Sursa){
bla=0;
for(i=0;i<l[S];i++)
{
if(d[v[S][i].vec]>d[S]+v[S][i].dist)
{
g<<"NU"<<'\n';
return;
}
if(d[S]==(d[v[S][i].vec]+v[S][i].dist)) bla=1;
}
if(!bla)
{
g<<"NU"<<'\n';
return;
}
}
g<<"DA"<<'\n';
return;
}
int main()
{
f>>t;
int i,a;
for(;t;--t)
{
f>>n>>m>>Sursa;
for(i=1;i<=n;i++)
{
f>>d[i];
l[i]=0;
while(!v[i].empty()) v[i].pop_back();
}
d[S]=0;
for(;m;--m)
{
f>>i>>aux.vec>>aux.dist;
v[i].push_back(aux);
a=i;i=aux.vec;aux.vec=a;
v[i].push_back(aux);
}
for(i=1;i<=n;i++) l[i]=v[i].size();
afisare();
}
}