Pagini recente » Cod sursa (job #952457) | Cod sursa (job #1588811)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define usi unsigned short int
#define Inf 2000000000
using namespace std;
int N, M, T, nodStart;
struct comp{
bool operator()(pair<usi, int> &a, pair<usi, int> &b){
return a.second > b.second;
}
};
vector< vector< pair<usi, int> > > A;
vector<int> d, dIn;
void initializare(int N, int M)
{
int x, y, c;
A.resize(N+1);
vector<int>().swap(dIn);
dIn.push_back(0);
for(int i=1; i<=N; i++){
scanf("%d", &x);
dIn.push_back(x);
}
while(M--){
scanf("%d%d%d", &x, &y, &c);
A[x].push_back(make_pair(y, c));
}
}
void Dijkstra(int nodStart)
{
int vec, cost, nOptim;
priority_queue<int, vector< pair<usi, int> >, comp> C;
d.assign(N+2,Inf);
d[nodStart]=0;
C.push(make_pair(nodStart, 0));
while(!C.empty()){
nOptim=C.top().first;
C.pop();
for(int i=0; i<A[nOptim].size(); i++)
{
//pentru fiecare nod pentru care exista muchie din nOptim in acel nod
vec = A[nOptim][i].first;
cost = A[nOptim][i].second;
if( d[vec] > d[nOptim] + cost)
{
//daca putem imbunatati costul drumului din nodStart in vecinul nodului optim prin nOptim
d[vec] = d[nOptim] + cost;
C.push(make_pair(vec, d[vec])); // adauga vecinul in coada cu prioritate
}
}
}
vector< vector<pair<usi, int> > >().swap(A); //erase
}
int main()
{
freopen("distante.in","rt",stdin);
freopen("distante.out","wt",stdout);
scanf("%d", &T);
for(int i=1; i<=T; i++)
{
scanf("%d%d%d", &N, &M, &nodStart);
initializare(N, M);
Dijkstra(nodStart);
int ok=1;
for(int i=1; i<=N; i++)
if(d[i] != dIn[i])
ok=0;
cout<<(ok==1 ? "DA\n" : "NU\n");
}
}