# PBinfo #616 – Zapada – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: andrei

## Enunț

Cerința
Orașul Kruskal are n intersecții unite prin m străzi bidirecționale. Datorită ninsorii de peste noapte, străzile sunt acoperite cu zăpadă. Administratorul orașului, Gigel, a determinat cu mari eforturi pentru fiecare stradă costul deszăpezirii ei și acum dorește deszăpezirea unor străzi astfel încât costul total al deszăpezirii lor să fie minim, și să se poată circula între oricare două intersecții pe străzi deszăpezite.

Maleficul Costel îl forțează pe Gigel să deszăpezească anumite străzi, din motive doar de el știute. Ajutați-l pe Gigel să determine costul minim pentru deszăpezirea orașului, astfel încât să fie deszăpezite străzile dorite de Costel și să se poată circula între oricare două intersecții pe străzi deszăpezite.

Date de intrare
Fișierul de intrare zapada.in conține pe prima linie numerele n m, iar pe următoarele m linii câte un triplet i j c, cu semnificația: există stradă între intersecțiile i j și are costul deszăpezirii egal cu  c. Urmează o linie care conține numărul k de străzi pe care Costel le dorește deszăpezite, iar următoarea linie conține k numere distincte între 1 și m, reprezentând numărul de ordine al străzilor care vor fi obligatoriu deszăpezite.

Date de ieșire
Fișierul de ieșire zapada.out va conține pe prima linie costul total minim al deszăpezirii orașului, în condițiile precizate.

Restricții și precizări

1 ≤ n ≤ 100
1 ≤ k < m ≤ n*(n-1)/2
costurile deszăpezirii străzilor sunt numere naturale nenule cel mult egale cu 1000
numerele celor k străzi care trebuie deszăpezite sunt dintre numerele de ordine ale celor m străzi date

Exemplu:
zapada.in

7 11
1 2 2
1 7 4
2 3 3
2 5 2
2 6 3
2 7 3
3 4 1
3 5 2
4 5 1
5 6 3
6 7 5
2
2 11
zapada.out

15
Explicație
Alături de străzile 1-7 și 6-7 care trebuie obligatoriu deszăpezite, se mai deszăpezesc străzile: 1-2, 2-5, 4-5 și 3-4. Costul total al deszăpezirii acestor străzi este 4+5+2+2+1+1=15

## Cod sursă C++

```cpp
#include <iostream>
#include <fstream>
#define INFINIT 1000000000
using namespace std;
ifstream fin("zapada.in");
ofstream fout("zapada.out");
struct muchie{
	int obl , i , j , cost;
};
int n , m , t[105];
muchie x[5000];
int main()
{
    fin >> n >> m;
    for(int i = 0 ; i < m ; ++i)
		fin >> x[i].i >> x[i].j >> x[i].cost;
	int k;
	fin >> k;
	for( ; k ; --k)
	{
		int i;
		fin >> i;
		x[i - 1].obl = 1;
	}
	for(int i = 0 ; i < m - 1; i ++)
		for(int j = i + 1 ; j < m ; ++j)
			if(x[i].obl < x[j].obl)
			{
				muchie aux = x[i];
				x[i] = x[j];
				x[j] = aux;
			}
			else
				if(x[i].obl == x[j].obl)
					if(x[i].cost > x[j].cost)
					{
						muchie aux = x[i];
						x[i] = x[j];
						x[j] = aux;
					}
	for(int i =1 ; i <= n ; ++i)
		t[i] = i;
	int S = 0;
	for(int i = 0 ; i < m ; i ++)
		if(x[i].obl == 1 || t[x[i].i] != t[x[i].j])
		{
			S += x[i].cost;
			if(t[x[i].i] != t[x[i].j])
			{
				int ai = t[x[i].i], aj = t[x[i].j];
				for(int j =1 ; j <= n ; ++j)
					if(t[j] == aj)
						t[j] = ai;
			}
		}
	fout << S << "\n";
	return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/616)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/616/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-616/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)