2933 - TollRoads

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 Q întrebări de forma: (X, T) – câte dintre celelalte N-1 orașe au acces către orașul X, cu o taxă totală de cel mult T către fiecare oraș?

Date de intrare

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

Date de ieșire

În fișierul de ieșire tollroads.out se vor scrie pe fiecare dintre primele Q 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

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

Exemplu:

tollroads.in

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

tollroads.out

6
5
3
3
5

Explicație

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

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

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

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

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

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>