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

6 10 3
1 5
1 2 3
1 3 2
2 4 3
2 5 2
3 4 1
4 5 3
4 6 2
5 1 2
5 6 2
6 5 1

anarhie.out

1

Explicație

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

#include <bits/stdc++.h>

using namespace std;

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

int n , m , p , q , x , y , r , k , X[12] , P[101] , S[101] , A[101][101] , mini = 999999999 , s;

int dfs(int c)
{
    P[c] = 1;
    for(int i = 1 ; i <= n ; i++)
        if(!P[i] && S[A[c][i]] && A[c][i])
            dfs(i);
}

int verif(int k)
{
    for(int i = 1 ; i <= n ; i++)
        S[i] = P[i] = 0;

    for(int i = 1 ; i <= k ; i++)
        S[X[i]] = 1;

    dfs(p);
    return P[q];
}

void back(int k)
{
    for(int i = X[k - 1] + 1 ; i <= s ; i++)
    {
        X[k] = i;
        if(verif(k))
            if(k < mini) mini = k;
        back(k + 1);
    }
}

int main()
{
    cin >> n >> m >> s;
    cin >> p >> q;
    for(int i = 1 ; i <= m ; i++)
    {
        cin >> x >> y >> r;
        A[x][y] = r;
    }
    back(1);
    cout << mini;
}