Pagini recente » Cod sursa (job #3153834) | Cod sursa (job #3288067) | Cod sursa (job #44887) | Cod sursa (job #2549943) | Cod sursa (job #1105689)
/*
* Created on: February 5th 2014
* Author: <Marin Andrei>
* Description: problema 2 oji 2011. clasele 11-12;
*/
#include <iostream>
#include <fstream>
using namespace std;
fstream f ("ubuntzei.in",ios::in);
fstream g ("ubuntzei.out",ios::out);
int viz[100];
int main (void)
{
int n,m,k,z,i,j,cost,NC=1,x,y,h,mini,NV;
long a[100][100],CT;
f>>n>>m;
f>>k;
for (i=1;i<=k;i++)
{f>>z;
viz[z]=1;}
//initializarea matricei
for (i=1;i<=n;++i)
for (j=1;j<=n;++j)
a[i][j]=100001;
for (i=1;i<=m;++i)
{
f>>x>>y>>z;
a[x][y]=a[y][x]=z;
}
/*for (i=1;i<=n;++i)
{
for (j=1;j<=n;++j)
//cout<<a[i][j]<<" ";
//cout<<endl;
}
*/
//aplicarea algoritm roy-floyd
for (h=1;h<=n;++h)
for (i=1;i<=n;++i)
for (j=1;j<=n;++j)
if (a[i][h]+a[h][j] < a[i][j])
a[i][j]=a[j][i]=a[i][h]+a[h][j];
CT=0;
NC=1;
for (h=1;h<=k;++h)
{
mini=100001;
for (i=1;i<=n;++i)
if (viz[i] && a[NC][i] < mini)
{
mini=a[NC][i];
NV=i;
}
/*for (i=1;i<=n;++i)
{for (j=1;j<=n;++j)
//cout<<a[i][j]<<" ";
//cout<<endl;}
*/
CT+=a[NC][NV];
//cout<<CT<<" ";
NC=NV;
viz[NV]=0;
}
CT+=a[NC][n];
//cout<<CT;
g<<CT;
f.close();
g.close();
return 0;
}