Pagini recente » Cod sursa (job #3145018) | Cod sursa (job #1037810) | Cod sursa (job #2066356) | Cod sursa (job #2473317) | Cod sursa (job #1428787)
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream ka("distante.in");
ofstream ki("distante.out");
const int N_MAX = 50000;
bool vazut[N_MAX + 1];
int t, n, m, s, a, b, c, distanta[N_MAX + 1];
struct muchie
{
int index, cost;
};
vector <muchie> graf[N_MAX + 1];
queue <int> coada;
string dijkstra()
{
coada.push(s);
while(!coada.empty())
{
int t = coada.front();
coada.pop();
if(!vazut[t])
{
vazut[t] = true;
for(int i = 0; i < graf[t].size(); i++)
{
if(distanta[t] + graf[t][i].cost == distanta[graf[t][i].index])
coada.push(graf[t][i].index);
}
}
}
for(int i = 1; i <= n; i++)
if(!vazut[i])
return "NU";
return "DA";
}
int main()
{
ka >> t;
for(int i = 1; i <= t; i++)
{
ka >> n >> m >> s;
for(int j = 1; j <= n; j++)
{
ka >> distanta[j];
vazut[j] = false;
graf[j].clear();
}
for(int j = 1; j <= m; j++)
{
ka >> a >> b >> c;
muchie mm;
mm.index = b;
mm.cost = c;
graf[a].push_back(mm);
mm.index = a;
graf[b].push_back(mm);
}
ki << dijkstra() << '\n';
}
}