Cod sursa(job #560144)

Utilizator cipri_tomCiprian Tomoiaga cipri_tom Data 18 martie 2011 12:43:29
Problema Distante Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 kb
#include <fstream>
#include <vector>
#include <set>
using namespace std;

#define DIM 50010
#define INF 0x3f3f3f3f
#define pb push_back
#define mp make_pair

ifstream fin("distante.in");
ofstream fout("distante.out");

int N, M, T;
int d[DIM];
int db[DIM];
int root;

vector <int> v[DIM];          //graful
vector <int> c[DIM];          //costul muchiilor
set < pair<int, int> > S;     // 

void Read();
void Dijkstra(int );
bool OK();

int main()
{
	fin >> T;
	for ( int i = 1; i <= T; ++i )
	{
		Read();
		Dijkstra(root);
		if ( OK() )
			fout << "DA\n";
		else
			fout << "NU\n";
		for ( int i = 0; i <= DIM; ++i )
			v[i].clear(), c[i].clear();
	}
	
	fin.close();
	fout.close();
	return 0;
}

void Read()
{
	memset (db, INF, sizeof(db) );
	fin >> N >> M >> root;
	for ( int i = 1; i <= N; ++i )
		fin >> db[i];
	int x, y, cost;
	for ( int i = 1; i <= M; ++i )
	{
		fin >> x >> y >> cost;
		v[x].pb(y);
		c[x].pb(cost);
		
		v[y].pb(x);
		c[y].pb(cost);
	}
}

bool OK()
{
	for ( int i = 1; i <= N; ++i )
		if ( d[i] != db[i] )
			return false;
	return true;
}

void Dijkstra ( int x )
{
	memset ( d, INF, sizeof(d) );
	d[x] = 0;
	S.insert ( mp ( 0, x ) );          //d[x] = 0, deci punem pe x in set
	
	int dmin, nod;
	int n;
	while ( S.size() )
	{
		dmin = (*S.begin()).first;     //extrag capul cozii
		nod = (*S.begin()).second;
		
		S.erase(*S.begin());           //sterg capul "cozii"
		n = v[nod].size();
		for ( int i = 0; i < n; ++i )  //parcurg vecinii nodului extras
		{
			int ve = v[nod][i];
			if ( d[ve] > d[nod] + c[nod][i] )
			{
				d[ve] = dmin + c[nod][i];
				S.insert( mp ( d[ve], ve ) );
			}
		}
	}
}