1895 - Festivaluri

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

Rezolvare

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()