Danciu: Pagină nouă: = Cerința = `N` orașe sunt conectate între ele prin `M` autostrăzi bidirecționale, fiecare autostradă `(a, b)` având un cost de tranzit `c` atașat. Se dorește revizuirea sistemului de taxare, însă sunt câteva aspecte ce trebuie luate în calcul și necesită investigație, deoarece o parte dintre cele `N` orașe sunt centre comerciale sau turistice importante. Se dorește să se afle răspunsul la o serie de...

2024-06-04T03:00:30Z

Pagină nouă: = Cerința = <code>N</code> orașe sunt conectate între ele prin <code>M</code> autostrăzi bidirecționale, fiecare autostradă <code>(a, b)</code> având un cost de tranzit <code>c</code> atașat. Se dorește revizuirea sistemului de taxare, însă sunt câteva aspecte ce trebuie luate în calcul și necesită investigație, deoarece o parte dintre cele <code>N</code> orașe sunt centre comerciale sau turistice importante. Se dorește să se afle răspunsul la o serie de...

New page

= Cerința =
<code>N</code> orașe sunt conectate între ele prin <code>M</code> autostrăzi bidirecționale, fiecare autostradă <code>(a, b)</code> având un cost de tranzit <code>c</code> atașat. Se dorește revizuirea sistemului de taxare, însă sunt câteva aspecte ce trebuie luate în calcul și necesită investigație, deoarece o parte dintre cele <code>N</code> orașe sunt centre comerciale sau turistice importante.

Se dorește să se afle răspunsul la o serie de <code>Q</code> întrebări de forma: <code>(X, T)</code> – câte dintre celelalte <code>N-1</code> orașe au acces către orașul <code>X</code>, cu o taxă totală de cel mult <code>T</code> către fiecare oraș?

= Date de intrare =
Fișierul de intrare <code>tollroads.in</code> conține pe primul rând numerele <code>N, M și Q</code> reprezentând numărul de orașe, numărul de autostrăzi și numărul de interogări. Pe fiecare din următoarele <code>M</code> rânduri sunt scrise câte trei numere <code>a, b, c,</code> separate prin câte un spațiu, reprezentând două orașe între care există o autostradă și costul autostrăzii. Pe următoarele <code>Q</code> rânduri se află scrise câte două numere <code>X</code> și <code>T</code>, separate prin spațiu, reprezentând datele interogărilor, conform enunțului.

= Date de ieșire =
În fișierul de ieșire <code>tollroads.out</code> se vor scrie pe fiecare dintre primele <code>Q</code> rânduri câte un singur număr, reprezentând răspunsurile la interogări, în ordinea în care ele au fost puse.

= Restricții și precizări =

* <code>1 ≤ N ≤ 100.000</code>
* <code>1 ≤ M ≤ 100.000</code>
* <code>1 ≤ a, b ≤ N</code>
* <code>1 ≤ c ≤ 100.000</code>
* <code>1 ≤ T ≤ 100.000</code>
* <code>1 ≤ Q ≤ 100</code>
* între orice două orașe poate exista mai mult de o autostrada

= Exemplu: =
<code>tollroads.in</code>
7 8 5
1 2 1
2 3 2
2 4 4
3 5 1
4 5 1
5 6 2
1 6 5
6 7 1
1 6
1 5
1 4
2 3
4 4
<code>tollroads.out</code>
6
5
3
3
5

=== Explicație ===
Orașele <code>2,3,4,5,6,7</code> au acces către orașul <code>1</code> cu taxă maximă <code>6</code>

Orașele <code>2,3,4,5,6</code> au acces către orașul <code>1</code> cu taxă maximă <code>5</code>

Orașele <code>2,3,5</code> au acces către orașul <code>1</code> cu taxă maximă <code>4</code>

Orașele <code>1,3,5</code> au acces către orașul <code>2</code> cu taxă maximă <code>3</code>

Orașele <code>2,3,5,6,7</code> au acces către orașul <code>4</code> cu taxă maximă <code>4</code>

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

INF = 2000000002

def main():
f = open("tollroads.in", "r")
g = open("tollroads.out", "w")

n, m, Q = map(int, f.readline().split())

graph = defaultdict(list)
for _ in range(m):
x, y, c = map(int, f.readline().split())
graph[x].append((y, c))
graph[y].append((x, c))

for _ in range(Q):
nod, taxa = map(int, f.readline().split())
dr = [INF] * (n + 1)
din = [[] for _ in range(taxa + 1)]

din[0].append(nod)
dr[nod] = sol = 0

viz = [False] * (n + 1)

for i in range(taxa + 1):
for nod in din[i]:
if viz[nod]:
continue
for ve, co in graph[nod]:
if dr[nod] + co > taxa or viz[ve]:
continue
if dr[ve] > dr[nod] + co:
dr[ve] = dr[nod] + co
din[dr[ve]].append(ve)
viz[nod] = True
din[i] = []

for i in range(1, n + 1):
viz[i] = False
if dr[i] != INF:
sol += 1

g.write(str(sol - 1) + '\n')

f.close()
g.close()

if __name__ == "__main__":
main()

</syntaxhighlight>

2933 - TollRoads - Revision history