Cod sursa(job #677533)

Utilizator micutuzBalog Adrian micutuz Data 10 februarie 2012 12:24:51
Problema Ubuntzei Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include<iostream>
#include<fstream>
#define DN 10005
using namespace std;
ifstream fin("ubuntzei.in");
ofstream fout("ubuntzei.out");

int n, m, d[DN], d2[DN], ks[DN], k, l=0;

struct nod
{
	int nod1, nod2, c;
	nod *urm;
}*a[2001], *p;

void creare(int x, int y, int cost)
{
	nod *q=new nod;
	q->nod1=x;
	q->nod2=y;
	q->c=cost;
	q->urm=a[1];
	a[1]=q;
}

int main()
{
	int i, ok=1,x,y,z;
	fin>>n>>m>>k;
	for(i=2;i<=n;i++)
		d[i]=999999;
	
	for(i=1;i<=k;i++)
		fin>>ks[i];
	
	for(i=1;i<=m;i++)
	{
		fin>>x>>y>>z;
		creare(x,y,z);
		if(x==1)
			d[y]=z;
	}
	
	while(ok)
	{
		p=a[1];ok=0;
		while(p)
		{
			if(d[p->nod2]>d[p->nod1]+p->c)
			{	
				d[p->nod2]=d[p->nod1]+p->c; ok=1;
				
			}
			p=p->urm;
		}
	}
	int j;
	for(j=1; j<=k;j++)
		l+=d[ks[j]];
	while(ok)
	{
		p=a[ks[k]];ok=0;
		while(p)
		{
			if(d2[p->nod2]>d2[p->nod1]+p->c)
			{	
				d2[p->nod2]=d2[p->nod1]+p->c; ok=1;
				
			}
			p=p->urm;
		}
	}
	fout<<l+d2[n];
}