Pagini recente » Borderou de evaluare (job #1037049) | Cod sursa (job #2164345)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define INF 0x3f3f3f3f
using namespace std;
ifstream f ("distante.in");
ofstream g ("distante.out");
struct edge
{
int y,cost;
};
int dist[50005];
struct cmp
{
bool operator()(int a, int b)
{
return dist[a]>dist[b];
}
};
priority_queue<int,vector<int>,cmp> heap;
void dij(int n, int m, int s, vector<edge> graf[])
{
bool ap[50005];
heap.push(s);
dist[s]=0;
while(!heap.empty())
{
int nod=heap.top();
heap.pop();
ap[nod]=0;
for(auto i:graf[nod])
{
if(dist[i.y]>dist[nod]+i.cost)
{
dist[i.y]=dist[nod]+i.cost;
if(!ap[i.y])
{
heap.push(i.y);
ap[i.y]=1;
}
}
}
}
}
int main()
{
int x;
f>>x;
for(int i=0;i<x;i++)
{
vector<edge> graf[50005];
int n,m,s;
f>>n>>m>>s;
int sablon[50005];
for(int i=1;i<=n;i++)
{
dist[i]=INF;
f>>sablon[i];
}
for(int j=0;j<m;j++)
{
int a,b,c;
f>>a>>b>>c;
graf[a].push_back({b,c});
graf[b].push_back({a,c});
}
dij(n,m,s,graf);
bool ok=0;
for(int i=1;i<=n&&ok==0;i++)
{
if(dist[i]==INF)
dist[i]=0;
if(dist[i]!=sablon[i])
{
g<<"NU"<<"\n";
ok=1;
}
}
if(ok==0)g<<"DA"<<"\n";
}
return 0;
}