Cod sursa(job #588928)

Utilizator t2011tVasilescu Popescu t2011t Data 10 mai 2011 09:21:18
Problema Distante Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <fstream>
#include <queue>
#include <vector>
#include <algorithm>
#define inf 2147000000
using namespace std;

struct s_node
{
vector <int> id;
vector <int> wg;
int val;
int ap_feud;
};

int n,m,k,feud[36000];
s_node node[36001];
queue <int> q;

int main()
{
ifstream in("catun.in");
ofstream out("catun.out");

int x,y,z;
int i1,i2,i3;
vector <int>::iterator it1,it2;

//citire
in>>n>>m>>k;
for(i1=0;i1<k;i1++)
	in>>feud[i1];

sort(feud,feud+k);

for(i1=0;i1<m;i1++)
	{
	in>>x>>y>>z;
	node[x].id.push_back(y);
	node[x].wg.push_back(z);
	node[y].id.push_back(x);
	node[y].wg.push_back(z);
	}
//

//initializare
for(i1=1;i1<=n;i1++)
	{
	node[i1].val = inf;
	}
//

//dijkstra
bool sw;

for(i3=0;i3<k;i3++) //pentru fiecare feuda(nod)
	{
	q.push(feud[i3]);
	node[feud[i3]].val = 0;
	while(!q.empty())
		{
		for(it1 = node[q.front()].id.begin(), it2 = node[q.front()].wg.begin(); //pentru fiecare nod adiacent
				it1!=node[q.front()].id.end();
				it1++,it2++)
				{
				sw = false;
				
				if(node[*it1].val > node[q.front()].val + *it2)
					sw = true;
				if(sw)
					{
					node[*it1].val = node[q.front()].val + *it2;
					node[*it1].ap_feud = feud[i3];
					q.push(*it1);
					}
				}
		q.pop();
		}
	}
//

//afisare
for(i1=0;i1<k;i1++)
	node[feud[i1]].ap_feud = 0;

for(i1=1;i1<=n;i1++)
	out<<node[i1].ap_feud<<' ';
//
in.close();
out.close();
return 0;
}