Copa do Mundo
A Nlogônia é atualmente um dos países com maior crescimento econômico no mundo, e seus governantes têm se esforçado para que o país seja mais conhecido e respeitado internacionalmente. Recentemente a Nlogônia foi escolhida para ser a sede da Copa do Mundo de Futebol Amador, e está se preparando para receber os milhares de torcedores que o evento atrai.
Como parte da preparação para a Copa, o governo planeja realizar uma reforma em todo o sistema de transporte intermunicipal, que é hoje composto de uma malha de rodovias e ferrovias, cada rodovia ou ferrovia interligando um par de cidades. Com as rodovias e ferrovias existentes já é possível viajar entre qualquer par de cidades (possivelmente passando por outras cidades no caminho), mas o governo quer oferecer melhores condições de transporte para os visitantes e a população.
Como não há recursos para reformar todas as rodovias e ferrovias, o governo quer escolher um conjunto de rodovias e ferrovias para ser reformado, e já realizou um estudo para estabelecer o custo de reforma de cada rodovia e ferrovia. A escolha deve obedecer aos seguintes critérios:
- ao final da reforma, deve ser possível viajar entre qualquer par de cidades (possivelmente passando por outras cidades) utilizando apenas rodovias ou ferrovias reformadas;
- para priorizar o transporte público, dentre as escolhas que satisfazem a restrição 1, deve-se escolher uma que minimize o número de rodovias reformadas;
- dentre as escolhas que satisfazem as restrições 1 e 2, deve-se escolher uma que minimize o custo total.
Você foi contratado para escrever um programa que, conhecidos os custos de reforma de cada rodovia e ferrovia, determine o menor custo possível para a reforma, obedecidos os critérios estabelecidos.
Entrada
A primeira linha da entrada contém três inteiros N, F e R, indicando respectivamente o número de cidades, de ferrovias e de rodovias. As cidades são identificadas por inteiros de 1 a N. Cada uma das F linhas seguintes descreve uma ferrovia e contém três inteiros A, B e C, onde A e B representam cidades e C representa o custo da reforma da ferrovia que interliga A e B. Cada uma das R linhas seguintes descreve uma rodovia e contém três inteiros I, J e K, onde I e J representam cidades e K representa o custo da reforma da rodovia que interliga I e J.Saída
Seu programa deve produzir uma única linha, contendo o menor custo possível para o conjunto de reformas de ferrovias e rodovias, obedecendo aos critérios estabelecidos.Restrições
- 2 ≤ N ≤ 100; 1 ≤ F ≤ N(N-1)/2; 1 ≤ R ≤ N(N-1)/2
- 1 ≤ A < B ≤ N e 1 ≤ I < J ≤ N
- 1 ≤ C ≤ 1000 e 1 ≤ K ≤ 1000
Informações sobre a pontuação
- Para um conjunto de casos de testes totalizando 20 pontos, 2 ≤ N ≤ 6.
Exemplos
Entrada
3 3 2 1 2 1000 1 3 1000 2 3 900 1 3 800 2 3 700 |
Saída
1900 |
Entrada
5 4 5 3 4 300 1 2 100 2 4 300 1 3 250 4 5 600 3 4 200 2 3 100 2 5 400 1 5 450 |
Saída
1050 |
Entrada
5 2 3 4 5 60 2 3 60 1 2 50 1 4 50 3 4 50 |
Saída
220 |
