Cod sursa(job #675482)

Utilizator NitaMihaitavoidcube NitaMihaita Data 7 februarie 2012 17:32:21
Problema Ubuntzei Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include<fstream>
#include<iostream>
using namespace std;
int a[2001][2001],c[2001],cost[2001],n,k,m,Ek[2001],magic[2001],viz[2001];
int main ()
{
ifstream f("ubuntzei.in");
ofstream g("ubuntzei.out");
int i,j,u,p;
f>>n>>m;
f>>k;
for(i=1;i<=k;i++)
	{
	f>>u;
	Ek[u]=1;
	}
while(f>>i>>j>>p)
	a[i][j]=a[j][i]=p;
c[1]=1;
cost[1]=magic[1]=0;
u=p=1;
p++;
while(u!=p)
	{
	if(u==1)p--;
	viz[c[u]]=1;
	for(i=1;i<=n;i++)
		if(a[c[u]][i] && viz[i]==0)
			{
			c[++p]=i;
			cost[p]=cost[u]+a[c[u]][i];
			magic[p]=magic[u]+Ek[i];
			}
	u++;
	}
u=1<<30;
for(i=1;i<=p;i++)
	if(c[i]==n and magic[i]==k)
		if(u>cost[i]) u=cost[i];
g<<u<<"\n";
return 0;
}
/*
link-uri:
http://infoarena.ro/problema/ubuntzei
http://infoarena.ro/job_detail/650855?action=view-source
http://infoarena.ro/problema/dijkstra
http://ro.wikipedia.org/wiki/Algoritmul_lui_Prim
*/