Cod sursa(job #197799)

Utilizator hadesgamesTache Alexandru hadesgames Data 6 iulie 2008 10:48:49
Problema Cautare binara Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include <stdio.h>
#include <vector>
#include <queue>
#include <list>
#include <set>
#include <algorithm>
#include <utility>
#include <string>
#include <functional>
using namespace std;
#define FOR(i,a,b) for (typeof a i=a;i<=b;i++)
#define fori(it,v) for (typeof ((v).begin()) it=(v).begin();it!=(v).end();it++)
#define pb push_back
#define mp make_pair
#define fs first
#define ss second
#define all(c) c.begin(),c.end()
typedef pair<int,pair<int,int> > ceva;
priority_queue<ceva ,vector<ceva>,greater<ceva > > q;
int n,m,k,x,y,z,ver[36005],pred[36005];
vector<int> b;
vector<vector<pair<int,int> > > a(36005);
int main()
{
	FILE *in,*out;
	in=fopen("catun.in","r");
	out=fopen("catun.out","w");
	fscanf(in,"%d%d%d",&n,&m,&k);
	FOR(i,1,k)
	{
		fscanf(in,"%d",&x);
		b.pb(x);
		q.push(mp(0,mp(x,x)));
	}
	FOR(i,1,m)
	{
		fscanf(in,"%d%d%d",&x,&y,&z);
		a[x].pb(mp(y,z));
		a[y].pb(mp(x,z));
	}
	while (!q.empty())
	{
		ceva aux=q.top();
		q.pop();
	//	printf("scos %d %d %d\n",aux.fs,aux.ss.fs,aux.ss.ss);
		if (!ver[aux.ss.fs])
		{
			pred[aux.ss.fs]=aux.ss.ss;
			ver[aux.ss.fs]=1;
			fori(it,a[aux.ss.fs])
			{
				if (!ver[it->fs])
				{
					q.push(mp(aux.fs+it->ss,mp(it->fs,aux.ss.ss)));

				}
			}
		}

	}
	fori(it,b)
		pred[*it]=0;
	FOR(i,1,n)
	{
		fprintf(out,"%d ",pred[i]);

	}
	fprintf(out,"\n");
	fclose(in);
	fclose(out);
	return 0;
}