Cerința

Tudor este foarte indecis, deoarece a fost chemat la r festivaluri și puterea lui fizică nu îi permite să ajungă la toate. În orașul în care locuiește sunt m străzi unidirecţionale și n intersecții numerotate cu numere de la 1 până la n. Festivalurile au loc în r intersecții. El pornește din intersecția cu numărul z.

Pentru a ajunge dintr-o intersecție în alta, folosește străzile. Când parcurge o stradă, el consumă o anumită energie, care diferă de la stradă la stradă.

După terminarea fiecărui festival, Tudor se va reîntoarce la casa lui, adică la intersecția cu numărul z, costul drumului de această dată fiind 0, pornind din nou la următorul festival.

Întrucât este un om foarte dedicat muzicii, Tudor vrea să participe la cât mai multe festivaluri, dar fără să-și depășească puterea lui fizică p.

Determinați numărul maxim de festivaluri la care poate participa.

Date de intrare

Fișierul de intrare festivaluri.in va conține pe prima linie numerele n, m, p, z, r. Pe următoarele m linii se vor afla câte 3 numere, reprezentând intersecția de unde începe strada, intersecția unde se termină strada și energia consumată pentru a parcurge strada. Pe următorul rând, se va afla cei r indici ai intersecțiilor unde se vor organiza festivalurile.

Date de ieșire

Fișierul de ieșire festivaluri.out va conține pe prima linie numărul cnt, reprezentând numărul maxim de festivaluri la care poate participa Tudor.

Restricții și precizări

• 1 ≤ n , m , z , r ≤ 100
• 1 ≤ p≤ 10.000
• numerele de pe cele m+1 linii a fișierului de intrare vor fi mai mici decât 100
• este posibil ca plecând din intersecția z să nu se poată ajunge în toate intersecțiile

Exemplu

festivaluri.in

7 5 9 2 2
1 2 3
2 4 1
4 5 2
1 4 1
5 7 2
3 5  

festivaluri.out

1

#include <bits/stdc++.h>



using namespace std;

ifstream cin("festivaluri.in");
ofstream cout("festivaluri.out");
using VVP = vector <vector <pair<int , int> > >;
using VI = vector <int>;
using PI = pair<int , int>;
VI d;
VVP G;
const int Inf = 0x3f3f3f3f;
int n , m , p , z , r , rez[101] , sum , cnt;

void Dijkstra(int x)
{
    d = VI(n + 1, Inf);
    priority_queue<PI, vector<PI>, greater<PI>> Q;
    int y , cost , dist;
    d[x] = 0;
    Q.push({0 , x});
    while(!Q.empty())
    {
        x = Q.top().second;
        dist = Q.top().first;
        Q.pop();
        if(dist > d[x]) continue;
        for(auto& p : G[x])
        {
            y = p.first;
            cost = p.second;
            if(d[y] > d[x] + cost)
            {
                d[y] = d[x] + cost;
                Q.push({d[y] , y});
            }
        }
    }
}

int main()
{
    cin >> n >> m >> p >> z >> r;
    G = VVP(n + 1);
    int x , y , w;
    for(int i = 1 ; i <= m ; i++)
    {
        cin >> x >> y >> w;
        G[x].push_back({y , w});
    }

    Dijkstra(z);
    for(int i = 1 ; i <= r ; i++)
    {
        cin >> x;
        rez[x] = d[x];
    }

    sort(rez + 1 , rez + n + 1);
    for(int i = 1 ; i <= n ; i++)
        if(rez[i] > 0)
        {
            if(sum + rez[i] < p) sum += rez[i] , cnt++;
            else break;
        }
    cout << cnt;
}