Pagini recente » Cod sursa (job #2724199) | Rating Teodoru Cosmin (costeo) | Cod sursa (job #2831445) | Cod sursa (job #495693) | Cod sursa (job #2534599)
#include <bits/stdc++.h>
using namespace std;
ifstream in("ubuntzei.in");
ofstream out("ubuntzei.out");
#define int long long
const int DIM = 2e3 + 5;
const int oo = 1e9;
int n, m, k;
bool ex[DIM];
int d[DIM];
int loc[DIM];
vector < pair <int, int> > l[DIM];
set <int> s;
struct cp
{
bool operator() (int x, int y)
{
return d[x] > d[y];
}
};
priority_queue <int,vector < int >, cp > c;
vector <pair <int,int> > l2[DIM];
void dijktra(int x)
{
for(int i = 1; i <= n; i++)
{
ex[i] = false;
d[i] = oo;
}
ex[x] = true;
d[x] = 0;
c.push(x);
while(!c.empty())
{
int nod = c.top();
c.pop();
ex[nod] = false;
for(int i = 0; i < l[nod].size(); i++)
{
int vec = l[nod][i].first;
int cost = l[nod][i].second;
if(d[nod] + cost < d[vec])
{
d[vec] = d[nod] + cost;
if(ex[vec] == false)
{
ex[vec] = true;
c.push(vec);
}
}
}
}
for(int i = 1; i <= n; i++)
{
if(d[i] != oo)
if(s.find(i)!= s.end())
{
l2[x].push_back(make_pair(i,d[i]));
}
}
}
priority_queue <pair <int, pair <int,int> > > c2;
bool viz[DIM];
void prim()
{
int rez = 0;
for(int i = 0; i < l2[1].size(); i++)
{
int nod = l2[1][i].first;
int cost = l2[1][i].second;
c2.push(make_pair(-cost,make_pair(1,nod)));
}
viz[1] = true;
int nr = 1;
while(nr < k && !c2.empty())
{
while(viz[c2.top().second.second])
c2.pop();
int nod = c2.top().second.second;
int cy = c2.top().first;
rez += cy;
nr++;
c2.pop();
viz[nod] = true;
for(int i = 0; i < l2[nod].size(); i++)
{
int vec = l2[nod][i].first;
int cost = l2[nod][i].second;
if(viz[vec] == false)
c2.push(make_pair(-cost,make_pair(nod,vec)));
}
}
out << -rez;
}
main()
{
in >> n >> m;
in >> k;
for(int i = 1; i <= k; i++)
{
in >> loc[i];
s.insert(loc[i]);
}
if(s.find(1) == s.end())
{s.insert(1);
k++;
loc[k] = 1;
}
if(s.find(n) == s.end())
{s.insert(n);
k++;
loc[k] = n;
}
for(int i = 1; i <= m; i++)
{
int x, y, z;
in >> x >> y >> z;
l[x].push_back(make_pair(y,z));
l[y].push_back(make_pair(x,z));
}
for(int i = 1; i <= k; i++)
{
dijktra(loc[i]);
}
prim();
return 0;
}