Pagini recente » Cod sursa (job #2640266) | Cod sursa (job #2650633) | Cod sursa (job #18288) | Cod sursa (job #1958586) | Cod sursa (job #2863935)
#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 b;
int szomszedok[k];
bool latogatando[csucsokSzama];
bool latogatott[k];
fill_n(latogatando, csucsokSzama, false);
fill_n(latogatott, k, false);
for (int i = 0; i < k ; i++)
{
f >> b;
szomszedok[i] = b - 1;
latogatando[b - 1] = true;
}
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 start = 0, mini, index, suly = 0;
for (int i = 0; i < k; i++)
{
mini = a;
index = -1;
sor.push(make_pair(0, start));
fill_n(hossz, csucsokSzama, a);
hossz[start] = 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);
}
}
}
for (int j = 0; j < csucsokSzama; j++)
{
if (latogatando[j] && !latogatott[j] && mini > hossz[j])
{
latogatott[j] = true;
mini = hossz[j];
index = j;
}
}
suly += mini;
start = index;
}
fill_n(hossz, csucsokSzama, a);
hossz[start] = 0;
sor.push(make_pair(0, start));
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);
}
}
}
suly += hossz[csucsokSzama - 1];
g << suly;
return 0;
}