Cerința

În imperiul maleficului Costel s-a instaurat anarhia. În imperiu sunt n orașe, numerotate de la 1 la n, unite prin m șosele unidirecționale, fiecare șosea fiind controlată de o bandă afiliată la unul dintre cele k sindicate banditești existente în imperiu, numerotate de la 1 la k. Pentru a călători prin pe șoselele din imperiu, orice călător trebuie să plătească taxe sindicatelor: plata taxei către un anumit sindicat îi permite călătorului să folosească nelimitat orice șosea controlată de o bandă afiliată acelui sindicat. Pentru toate sindicatele se plătește aceeași taxă.

Călătorul Gigel trebuie să ajungă din orașul p în orașul q. Determinați numărul minim de sindicate banditești cărora Gigel trebuie să le plătească taxe, pentru a putea realiza călătoria dorită.

Date de intrare

Fișierul de intrare anarhie.in conține pe prima linie numerele n m k. A doua linie conține numerele p q. Fiecare dintre următoarele m linii conține un triplet i j s, cu semnificația: între orașul i și orașul j există o șosea unidirecțională controlată de o bandă afiliată sindicatului s.

Date de ieșire

Fișierul de ieșire anarhie.out va conține pe prima linie numărul Z, reprezentând numărul minim de sindicate cărora trebuie plătită taxă pentru călătoria din orașul p în orașul q.

Restricții și precizări

1 ≤ n ≤ 100
1 ≤ m ≤ n*(n-1)
1 ≤ k ≤ 10
1 ≤ p, q ≤ n, p ≠ q
1 ≤ i ≤ n, 1 ≤ j ≤ n, 1 ≤ s ≤ k, i ≠ j

Exemplu

anarhie.in

anarhie.out

Explicație

Gigel va călătoria pe traseul 1 2 4 5, plătind taxă sindicatului 3.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Anarhie:

#include <iostream>
#include <fstream>
using namespace std;

ifstream fin("anarhie.in");
ofstream fout("anarhie.out");

int n , m , K , p, q , a[105][105], 
    x[105], // backtracking
    z[105], // vector caracteristic, pentru sindicatele din submultimea curenta
    v[105], // vizitati pentru parcurgere
    rasp = 1000
    ;

/*
 * Generez toate submultimile de sindicate, si pentru fiecare submultime verific 
 * daca poate fi parcurs traseul folosind doar sindicatele din acea submultime
 * O( 2^k * n^2)
 * */

void citire()
{
    fin >> n >> m >> K;
    fin >> p >> q;
    int i , j , s;
    for(int k = 1 ; k <= m ; ++k)
    {
        fin >> i >> j >> s;
        a[i][j] = s;
    }
}

int DF(int x)
{
    if(x == q)
        return 1;
    v[x] = 1;
    int rez = 0;
    for(int i = 1 ; i <= n ; ++i)
        if(v[i] == 0 && z[a[x][i]] == 1)
            rez |= DF(i);
    return rez;
}

int verif(int k)
{
    for(int i = 1 ; i <= n ; ++i)
        v[i] = z[i] = 0;
    for(int i = 1 ; i <= k ; ++i)
        z[x[i]] = 1;
    int pot = DF(p);
    return pot;
}

void back(int k)
{
    for(int i = x[k-1] + 1  ; i <= K ; i ++)
    {
        x[k] = i;
        if(verif(k))
        {
            if(rasp > k)
                rasp = k;
        }
        back(k+1);
    }
}

int main()
{
    citire();
    back(1);
    fout << rasp;
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #595 Anarhie

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #595 Anarhie de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #595 Anarhie