Pagini recente » Cod sursa (job #2146474) | Cod sursa (job #2513655) | Cod sursa (job #2108890) | Cod sursa (job #309216) | Cod sursa (job #2858982)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f ("ubuntzei.in");
ofstream g ("ubuntzei.out");
int n, m, lg;
bool v[2005];
int a[2005][2005];
int tata[2005];
bool u[2005];
const int inf = 2e9;
int nr_muchii;
struct muchie {
int x, y, cost;
}muchii[10005];
bool cmp (muchie a, muchie b)
{
if (a.cost <= b.cost)
return true;
return false;
}
int Radacina (int nod)
{
if (tata[nod] == 0)
return nod;
int k = Radacina(tata[nod]);
tata[nod] = k;
return k;
}
void Uneste (int x, int y)
{
int rx = Radacina(x); int ry = Radacina(y);
tata[ry] = rx;
}
int main()
{
f >> n >> m >> lg;
for (int i=1; i<=lg; i++)
{
int x; f >> x;
v[x] = 1;
}
for (int i=1; i<=n; i++)
for (int j=1; j<=n; j++)
a[i][j] = inf;
for (int i=1; i<=n; i++)
tata[i] = 0;
while (m --)
{
int i, j, c;
f >> i >> j >> c;
a[i][j] = a[j][i] = c;
}
for (int k=1; k<=n; k++)
{
for (int i=1; i<=n; i++)
{
for (int j=1; j<=n; j++)
{
if (i != j && a[i][k] != inf && a[j][k] != inf)
if (a[i][k] + a[k][j] < a[i][j])
a[i][j] = a[i][k] + a[k][j];
}
}
}
v[1] = 1; v[n] = 1;
int bound = 0;
for (int i=1; i<=n; i++)
if (v[i]) bound ++;
for (int i=1; i<=n; i++)
{
if (v[i] == 1)
{
for (int j=1; j<=n; j++)
{
if (v[j] && i != j)
{
nr_muchii ++;
muchii[nr_muchii] = {i, j, a[i][j]};
}
}
}
}
sort(muchii+1, muchii+nr_muchii+1, cmp);
int sum = 0;
int nrMuchii = 0;
for (int i=1; i<=nr_muchii; i++)
{
int x = muchii[i].x;
int y = muchii[i].y;
int cost = muchii[i].cost;
if (Radacina(x) != Radacina(y))
{
Uneste(x, y);
sum += cost;
nrMuchii ++;
}
if (nrMuchii == bound-1) break;
}
g << sum;
return 0;
}