Danciu: Pagină nouă: = 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ți...

2024-06-04T01:53:51Z

Pagină nouă: = 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ți...

New page

= 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>

1895 - Festivaluri - Revision history