Pagini recente » Cod sursa (job #3262978) | Cod sursa (job #1025622) | Cod sursa (job #2527781) | Cod sursa (job #1451980) | Cod sursa (job #2863781)
#include <iostream>
#include <fstream>
#include <list>
#include <queue>
using namespace std;
int a = 2147483647;
int main()
{
fstream f("ubuntzei.in");
ofstream g("ubuntzei.out");
int csucsokSzama, elekSzama;
f >> csucsokSzama >> elekSzama;
int k;
f >> k;
int szomszedok[k + 1];
for (int i = 1; i < k + 1; i++)
{
f >> szomszedok[i];
szomszedok[i]--;
}
szomszedok[0] = 0;
int x, y, z;
list<pair <int, int> > csucsok[csucsokSzama];
list<pair <int, int> > :: iterator it;
for (int i = 0; i < elekSzama; i++)
{
f >> x >> y >> z;
csucsok[x - 1].push_back(make_pair(z, y - 1));
csucsok[y - 1].push_back(make_pair(z, x - 1));
}
priority_queue<pair <int, int>, vector<pair <int, int> >,greater<pair <int, int> > > sor;
sor.push(make_pair(0, 0));
int hossz[csucsokSzama];
pair <int, int> elem;
int suly = 0;
for (int i = 0; i < k + 1; i++)
{
sor.push(make_pair(0, szomszedok[i]));
fill_n(hossz, csucsokSzama, a);
hossz[szomszedok[i]] = 0;
while(!sor.empty())
{
elem = sor.top();
sor.pop();
for(it = csucsok[elem.second].begin(); it != csucsok[elem.second].end(); it++)
{
if (hossz[elem.second] + it->first < hossz[it->second])
{
hossz[it->second] = hossz[elem.second] + it->first;
sor.push(*it);
}
}
}
if (i < k)
{
suly += hossz[szomszedok[i + 1]];
}
else
{
suly += hossz[csucsokSzama - 1];
}
}
g << suly;
return 0;
}