Cod sursa(job #680194)

Utilizator noobakafloFlorin eu noobakaflo Data 14 februarie 2012 12:04:43
Problema Ubuntzei Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
#include<stdio.h>
#include<vector>
#include<queue>
using namespace std;

#define MAX_N 2001
#define mp make_pair
#define INF 9999999

int n,m,k,prieteni[MAX_N],d[MAX_N],t[MAX_N];
vector<int> drum;
vector < pair<int,int> > gr[MAX_N];

void read(void)
{
	freopen("ubuntzei.in","r",stdin);
	int i,x,y,c;
	scanf("%d %d %d",&n,&m,&k);
	for(i=1; i<=k; i++)
		scanf("%d",&prieteni[i]);
	
	for(i=1; i<=m; i++)
	{
		scanf("%d %d %d",&x,&y,&c);
		gr[x].push_back(mp(y,c));
		gr[y].push_back(mp(x,c));
	}
}

void bellman_ford(int start)
{
	int i,x;  queue<int> C;
	vector < pair<int,int> > ::iterator it;
	for(i=2; i<=n; i++)
		d[i]=INF;   
	C.push(start);
	while(!C.empty())
	{
		x=C.front();
		C.pop();
		
		for(it=gr[x].begin(); it!=gr[x].end(); it++)
			if(d[it->first]>d[x]+it->second)
			{
				d[it->first]=d[x]+it->second;
				t[it->first]=x;
				C.push(it->first);
			}
	}
}

void build_path(int nod)
{
	if(t[nod])
		build_path(t[nod]);
	drum.push_back(nod);
}

int solve_length()
{
	int L=0;
	vector<int> ::iterator i;
	vector< pair<int,int> > ::iterator j;
	
	for(i=drum.begin(); i!=drum.end(); i++)
		if(*i!=drum.back())
		{
		   for(j=gr[*i].begin(); j!=gr[*i].end(); j++)
			   if(j->first==*(i+1))
			   {
				   L+=j->second;
				   break;
			   }
		}
	return L;
}
		
	

void write(void)
{
	freopen("ubuntzei.out","w",stdout);
	printf("%d ",solve_length());
	
}
	

int main()
{
	read();
	bellman_ford(1);
	build_path(n);
	write();
	return 0;
}