Pagini recente » Cod sursa (job #2479727) | Cod sursa (job #676606) | Cod sursa (job #2519336) | Cod sursa (job #3244062) | Cod sursa (job #675482)
Cod sursa(job #675482)
#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
*/