Pagini recente » Cod sursa (job #1355603) | Cod sursa (job #2198526) | Cod sursa (job #2120296) | Cod sursa (job #2392416)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream f("distante.in");
ofstream g("distante.out");
int t,d[50005],n,m,s;
vector < pair<int,int> > a[50005];
string check()
{
int i,j;
bool sw;
for(i=1;i<=n;i++)
{
if(i==s)
{
sw=1;
}
else
{
sw=0;
}
for(j=0;j<a[i].size();j++)
{
if(d[a[i][j].first]>d[i]+a[i][j].second)
{
return "NU\n";
}
if(i!=s)
{
if(d[i]==d[a[i][j].first]+a[i][j].second)
{
sw=1;
}
}
}
if(sw==0)
{
return "NU\n";
}
}
return "DA\n";
}
int main()
{
int i,j,x,y,cost;
f>>t;
while(t--)
{
f>>n>>m>>s;
for(i=1;i<=n;i++)
{
f>>d[i];
}
while(m--)
{
f>>x>>y>>cost;
a[x].push_back({y,cost});
a[y].push_back({x,cost});
}
g<<check();
for(i=1;i<=n;i++)
{
a[i].clear();
}
}
return 0;
}