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

#include <bits/stdc++.h>

using namespace std;

ifstream cin("zapada.in");
ofstream cout("zapada.out");

int n , m , T[101] , t , cnt , x , y , c , k;

struct poz
{
    int i , j , c;
}E[1001];

poz A[101];

void leaga(int a , int b)
{
    T[a] = T[b];
}

int radacina(int a)
{
    if(a == T[a]) return a;
    else return T[a] = radacina(T[a]);
}

void kruskal()
{
    int r1 , r2;
    for(int i = 1 ; i <= m ; i++)
    {
        r1 = radacina(E[i].i);
        r2 = radacina(E[i].j);
        if(r1 != r2)
        {
            t += E[i].c;
            A[++cnt] = E[i];
            leaga(r1 , r2);
        }
    }
}

int comp(poz a , poz b)
{
    if(a.c < b.c) return 1;
    else if(a.c == b.c && a.i < b.i) return 1;
    else if(a.c == b.c && a.i == b.i && a.j < b.j) return 1;
    else return 0;
}

int main()
{
    cin >> n >> m;
    for(int i = 1 ; i <= n ; i++)
        T[i] = i;

    for(int i = 1 ; i <= m ; i++)
    {
        cin >> x >> y >> c;
        E[i].i = x;
        E[i].j = y;
        E[i].c = c;
    }
    cin >> k;
    for(int i = 1 ; i <= k ; i++)
    {
        cin >> x;
        A[++cnt] = E[x];
        t += E[x].c;
        int r1 = radacina(E[x].i);
        int r2 = radacina(E[x].j);
        leaga(r1 , r2);
    }
    sort(E + 1 , E + m + 1 , comp);
    kruskal();
    cout << t << '\n';
}