Cod sursa(job #2476952)

Utilizator gazdac_alex@yahoo.comGazdac Alexandru Eugen [email protected] Data 19 octombrie 2019 13:08:24
Problema Ubuntzei Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.93 kb
#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;
}