Pagini recente » Cod sursa (job #2799315) | Cod sursa (job #2416163) | Cod sursa (job #817880) | Cod sursa (job #1718038) | Cod sursa (job #1624195)
#include<fstream>
#define inf 1<<30
using namespace std;
ifstream f("ubuntzei.in");
ofstream g("ubuntzei.out");
int n,m,i,k,d[2005],xx,j,fin,nod,poz,val;
struct localitati
{
int x,y,c;
}a[20005];
bool viz[2005],ok;
void dijkstra()
{
for(i=1;i<=n;i++)
d[i]=inf;
d[nod]=0;
for(i=1;i<=m;i++)
if(a[i].x==nod)
d[a[i].y]=a[i].c;
do
{
ok=1;
for(i=1;i<=m;i++)
if(d[a[i].y]>d[a[i].x]+a[i].c)
{
d[a[i].y]=d[a[i].x]+a[i].c;
ok=0;
}
}while(ok==0);
poz=0;
val=inf;
for(i=1;i<=n;i++)
if(viz[i]==1)
{
if(d[i]<val)
{
poz=i;
val=d[i];
}
}
if(poz!=0)
{
viz[poz]=0;
nod=poz;
fin+=val;
}
else
{
nod=n;
fin+=d[n];
}
}
int main()
{
f>>n>>m;
f>>k;
for(int i=1;i<=k;i++)
{
f>>xx;
viz[xx]=1;
}
for(int i=1;i<=m;i++)
{
f>>a[i].x>>a[i].y>>a[i].c;
a[i+m].y=a[i].x;
a[i+m].x=a[i].y;
a[i+m].c=a[i].c;
}
m*=2;
nod=1;
while(nod!=n)
dijkstra();
g<<fin;
return 0;
}