#include <iostream>
#include <vector>
#include <queue>
#include <limits>
const double INF = 1e9;
class FilaPrioridadeMinima {
private:
using Elemento = std::pair<double, int>;
struct Comparador {
bool operator()(const Elemento& a, const Elemento& b) {
return a.first > b.first;
}
};
std::priority_queue<Elemento, std::vector<Elemento>, Comparador> heap;
public:
void inserir(int vertice, double distancia) {
heap.push(std::make_pair(distancia, vertice));
}
bool vazia() const {
return heap.empty();
}
Elemento remover() {
Elemento topo = heap.top();
heap.pop();
return topo;
}
};
class Grafo {
private:
int ordem;
std::vector<std::vector<std::pair<int, double>>> adjacencias;
public:
Grafo(int n) : ordem(n), adjacencias(n) {}
std::vector<std::pair<int, double>> obterVizinhos(int vertice){ return
adjacencias[vertice]; };
void adicionarAresta(int origem, int destino, double peso) {
adjacencias[origem].emplace_back(destino, peso);
adjacencias[destino].emplace_back(origem, peso);
}
std::vector<double> dijkstra(int inicio, std::vector<int>& predecessores) {
std::vector<double> distancia(ordem, INF);
predecessores.resize(ordem, -1);
distancia[inicio] = 0.0;
FilaPrioridadeMinima filaPrioridade;
filaPrioridade.inserir(inicio, 0.0);
while (!filaPrioridade.vazia()) {
int u = filaPrioridade.remover().second;
for (const auto& vizinho : adjacencias[u]) {
int v = vizinho.first;
double pesoUV = vizinho.second;
if (distancia[u] + pesoUV < distancia[v]) {
distancia[v] = distancia[u] + pesoUV;
predecessores[v] = u;
filaPrioridade.inserir(v, distancia[v]);
}
}
}
return distancia;
}
std::vector<int> obterCaminhoMinimo(int inicio, int destino, const
std::vector<int>& predecessores) {
std::vector<int> caminho;
for (int v = destino; v != -1; v = predecessores[v]) {
caminho.insert(caminho.begin(), v); // Insere no inicio do vetor
}
return caminho;
}
};
bool fazParteDoCaminhoMinimo(const std::vector<int>& caminhoMinimo, int bloco) {
for (int vertice : caminhoMinimo) {
if (vertice == bloco) {
return true;
}
}
return false;
};
class UnionFind {
private:
std::vector<int> pai, tamanho;
public:
UnionFind(int n);
int encontrar(int elemento);
void unir(int elemento1, int elemento2);
};
UnionFind::UnionFind(int n) : pai(n), tamanho(n, 1) {
for (int i = 0; i < n; ++i) {
pai[i] = i;
}
}
int UnionFind::encontrar(int elemento) {
if (pai[elemento] != elemento) {
pai[elemento] = encontrar(pai[elemento]);
}
return pai[elemento];
}
void UnionFind::unir(int elemento1, int elemento2) {
int raiz1 = encontrar(elemento1);
int raiz2 = encontrar(elemento2);
if (raiz1 != raiz2) {
if (tamanho[raiz1] < tamanho[raiz2]) {
std::swap(raiz1, raiz2);
}
pai[raiz2] = raiz1;
tamanho[raiz1] += tamanho[raiz2];
}
};
int main() {
bool fazParteDoCaminhoMinimo(const std::vector<int>& caminhoMinimo,int bloco);
int ordemGrafo, tamanhoGrafo;
std::cin >> ordemGrafo >> tamanhoGrafo;
Grafo grafoCerebro(ordemGrafo);
for (int i = 0; i < tamanhoGrafo; ++i) {
int origem, destino;
double peso;
std::cin >> origem >> destino >> peso;
grafoCerebro.adicionarAresta(origem - 1, destino - 1, peso);
}
int blocoEntrada, blocoSaida;
std::cin >> blocoEntrada >> blocoSaida;
std::vector<int> predecessores;
std::vector<double> distancia = grafoCerebro.dijkstra(blocoEntrada - 1,
predecessores);
std::vector<int> caminho = grafoCerebro.obterCaminhoMinimo(blocoEntrada - 1,
blocoSaida - 1, predecessores);
int numeroBlocos;
numeroBlocos = ordemGrafo;
double somaPesosMST = 0.0;
std::vector<bool> blocoComNeuroniosDoentes(numeroBlocos, false);
for (int bloco = 0; bloco < numeroBlocos; ++bloco) {
int ordemBloco, tamanhoBloco;
std::cin >> ordemBloco >> tamanhoBloco;
int numeroNeuroniosDoentes;
std::cin >> numeroNeuroniosDoentes;
for (int i = 0; i < numeroNeuroniosDoentes; ++i) {
int neuronioDoente;
std::cin >> neuronioDoente;
blocoComNeuroniosDoentes[bloco] = true;
}
Grafo grafoBloco(ordemBloco);
for (int i = 0; i < tamanhoBloco; ++i) {
int origem, destino;
double peso;
std::cin >> origem >> destino >> peso;
grafoBloco.adicionarAresta(origem - 1, destino - 1, peso);
}
double pesoMSTBloco = 0.0;
// Aplicar o algoritmo de Kruskal apenas se o bloco tiver neurônios doentes
if (blocoComNeuroniosDoentes[bloco] &&
fazParteDoCaminhoMinimo(caminho,bloco)) {
UnionFind unionFind(ordemBloco);
// Estrutura para armazenar as arestas do grafoBloco
std::vector<std::pair<double, std::pair<int, int>>> arestas;
for (int vertice = 0; vertice < ordemBloco; ++vertice) {
for (auto vizinho : grafoBloco.obterVizinhos(vertice)) {
int verticeVizinho = vizinho.first;
double peso = vizinho.second;
// Armazena a aresta (peso, (vertice, verticeVizinho))
arestas.push_back({peso, {vertice, verticeVizinho}});
}
}
// Ordena as arestas pelo peso em ordem crescente
for (size_t i = 0; i < arestas.size(); ++i) {
for (size_t j = 0; j < arestas.size() - i - 1; ++j) {
if (arestas[j].first > arestas[j + 1].first) {
std::swap(arestas[j], arestas[j + 1]);
}
}
}
for (const auto& aresta : arestas) {
double peso = aresta.first;
int vertice1 = aresta.second.first;
int vertice2 = aresta.second.second;
// Verifica se a inclusão da aresta não forma um ciclo
if (unionFind.encontrar(vertice1) != unionFind.encontrar(vertice2))
{
pesoMSTBloco += peso;
unionFind.unir(vertice1, vertice2);
}
}
}
// Adiciona o custo da MST do bloco ao custo total da MST dos blocos
somaPesosMST += pesoMSTBloco;
std::cout << "Soma dos Pesos MST: " << somaPesosMST;
return 0;
}
