Pagini recente » Cod sursa (job #2365258) | Cod sursa (job #1536013) | Cod sursa (job #743785) | Cod sursa (job #769470) | Cod sursa (job #768470)
Cod sursa(job #768470)
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#define N 2010
#define PI pair<pair<int,int>,int>
#define x first.first
#define y first.second
#define cs second
#define mp make_pair
#define INF 999999999
using namespace std;
ifstream f("ubuntzei.in");
ofstream g("ubuntzei.out");
int n,i,j,m,a,b,c,d[15][N],k,C[N][N],ANS,GR[N],PR[N];
bool K[N],IQ[N];
vector<int> A[N];
queue<int> Q;
vector<PI> V;
bool Comp (PI a, PI b)
{
return a.cs<b.cs;
}
int BF (int s)
{
int nod,j;
Q.push(s);
IQ[s]=1;
d[s][s]=0;
while (!Q.empty())
{
nod=Q.front();Q.pop();
IQ[nod]=0;
for (j=0;j<A[nod].size();j++)
if (d[s][nod]+C[nod][A[nod][j]]<d[s][A[nod][j]])
{
d[s][A[nod][j]]=d[s][nod]+C[nod][A[nod][j]];
if (IQ[A[nod][j]]) continue;
IQ[A[nod][j]]=1;
Q.push(A[nod][j]);
}
}
}
int rad (int a)
{
int p,b;
for (p=a;p!=PR[p];p=PR[p]);
for (;a!=PR[a];)
{
b=PR[a];
PR[a]=p;
a=b;
}
return p;
}
void unite (int a, int b)
{
if (GR[a]>=GR[b]) PR[b]=a;
else PR[a]=b;
if (GR[a]==GR[b]) GR[a]++;
}
int main ()
{
f >> n >> m;
f >> k;
for (i=1;i<=k;i++)
{
f >> a;
K[a]=1;
}
for (i=0;i<15;i++)
for (j=0;j<=n;j++) d[i][j]=INF;
for (i=1;i<=m;i++)
{
f >> a >> b >> c;
A[a].push_back(b);
A[b].push_back(a);
C[a][b]=C[b][a]=c;
}
for (i=1;i<=n;GR[i]=1,PR[i]=i,i++)
if (K[i]==1)
BF(i);
/*for (i=1;i<=n;i++)
{
for (j=1;j<=n;j++) g << d[i][j] << ' ';
g << '\n';
}*/
for (i=1;i<=n;i++)
for (j=i+1;j<=n;j++)
{
if (i!=1 && i!=n && K[i]==0) continue;
if (j!=1 && j!=n && K[j]==0) continue;
V.push_back(mp(mp(i,j),(K[i]==1?d[i][j]:d[j][i])));
}
sort(V.begin(),V.end(),Comp);
for (i=0;i<V.size();i++)
{
a=V[i].x;b=V[i].y;c=V[i].cs;
if (rad(a)==rad(b)) continue;
ANS+=c;
unite(rad(a),rad(b));
}
g << ANS << '\n';
f.close();g.close();
return 0;
}