Editing 1895 - Festivaluri


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

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 <code>z</code>, costul drumului de această dată fiind <code>0</code>, 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ă <code>p</code>.

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

= Date de intrare =
Fișierul de intrare <code>festivaluri.in</code> va conține pe prima linie numerele <code>n</code>, <code>m</code>, <code>p</code>, <code>z</code>, <code>r</code>. Pe următoarele <code>m</code> linii se vor afla câte <code>3</code> 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 <code>r</code> indici ai intersecțiilor unde se vor organiza festivalurile.

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

= Restricții și precizări =

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

= Exemplu: =
<code>festivaluri.in</code>
 7 5 9 2 2
 1 2 3
 2 4 1
 4 5 2
 1 4 1
 5 7 2
 3 5  
<code>festivaluri.out</code>
 1

== Rezolvare ==
<syntaxhighlight lang="python3">
from collections import defaultdict, deque

class InParser:
    def __init__(self, nume):
        self.fin = open(nume, "r")

    def read_int(self):
        return int(self.fin.readline())

    def read_values(self):
        return map(int, self.fin.readline().split())

class OutParser:
    def __init__(self, nume):
        self.fout = open(nume, "w")

    def write(self, s):
        self.fout.write(s)

class Graph:
    def __init__(self, n):
        self.adj_list = defaultdict(list)
        self.n = n

    def add_edge(self, u, v, cost):
        self.adj_list[u].append((v, cost))

def max_festivals(n, m, p, z, r, streets, festivals):
    graph = Graph(n)

    for start, end, cost in streets:
        graph.add_edge(start, end, cost)

    visited = set()
    festivals_set = set(festivals)
    queue = deque([(z, 0, p)])  # (current_intersection, current_energy_spent, remaining_energy)

    cnt = 0
    while queue:
        intersection, energy_spent, remaining_energy = queue.popleft()

        if intersection in festivals_set:
            cnt += 1

        if cnt == r:
            return cnt

        if energy_spent > remaining_energy:
            continue

        for neighbor, cost in graph.adj_list[intersection]:
            new_energy_spent = energy_spent + cost
            if new_energy_spent <= p and neighbor not in visited:
                queue.append((neighbor, new_energy_spent, p - new_energy_spent))
                visited.add(neighbor)

    return cnt

fin = InParser("festivaluri.in")
fout = OutParser("festivaluri.out")

n, m, p, z, r = fin.read_values()
streets = [tuple(fin.read_values()) for _ in range(m)]
festivals = list(fin.read_values())

cnt = max_festivals(n, m, p, z, r, streets, festivals)
fout.write(str(cnt) + "\n")

fout.fout.close()

</syntaxhighlight>