Pagini recente » Istoria paginii runda/guta_contest | Istoria paginii runda/a-c-d/clasament | Monitorul de evaluare | Statistici Marin Florin Eduard Marian (Meepo) | Cod sursa (job #2476952)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
fstream in("ubuntzei.in");
ofstream out("ubuntzei.out");
int const maxim = 100005;
int const oo = (1 << 30);
int n, m, k;
int localitati[maxim];
int distanta[maxim];
bool in_coada[maxim];
bool vizitat[maxim];
vector< pair<int,int> > stocare[maxim];
struct compara {
bool operator()(int x, int y) {
return distanta[x] < distanta[y];
}
};
priority_queue <int, vector<int>, compara > coada;
void dijkstra(int nod_start) {
for (int i = 1; i <= n; i++) {
distanta[i] = oo;
}
distanta[nod_start] = 0;
coada.push(nod_start);
in_coada[nod_start] = true;
while (!coada.empty()) {
int nod_curent = coada.top();
in_coada[nod_curent] = false;
coada.pop();
for (auto x: stocare[nod_curent]) {
int vecin = x.first;
int cost = x.second;
if (distanta[vecin] > distanta[nod_curent] + cost) {
distanta[vecin] = distanta[nod_curent] + cost;
if (in_coada[vecin] == false) {
coada.push(vecin);
in_coada[vecin] = true;
}
}
}
}
}
int main() {
in >> n >> m >> k;
for (int i = 1; i <= k; i++) {
in >> localitati[i];
}
for (int i = 1; i <= m; i++) {
int a, b, c;
in >> a >> b >> c;
stocare[a].push_back(make_pair(b, c));
stocare[b].push_back(make_pair(a, c));
}
dijkstra(n);
bool okay = true;
int distanta_totala = 0;
int nod_actual;
while (okay) {
int distanta_actuala = oo;
okay = false;
for (int i = 1; i <= k; i++) {
if ((distanta[localitati[i]] < distanta_actuala) && (vizitat[localitati[i]] == false)) {
distanta_actuala = distanta[localitati[i]];
nod_actual = localitati[i];
}
if (vizitat[localitati[i]] == false) okay = true;
}
if (distanta_actuala != oo)
{
distanta_totala += distanta_actuala;
dijkstra(nod_actual);
vizitat[nod_actual] = true;
}
}
out << distanta_totala+1;
return 0;
}