3547 - vacanta2020

Cerința

În anul 2020, profitând de lipsa oamenilor de pe şosele, guvernul a construit atâtea şosele încât poţi ajunge din orice oraş al patriei în oricare altul. Drumul dintre două oraşe are şi un cost, cel al benzinei consumate. Dorel s-a hotărât să plece într-o excursie, pornind din oraşul 1 până într-un oraş oarecare. El profită şi de oferta guvernului de relansare a turismului, având k vouchere de călătorie. Un voucher îl scuteşte de plata benzinei între două oraşe consecutiv vizitate, traseu pe care îl alege el pentru scutirea plăţii, de asemenea nefiind obligatorie folosirea tuturor voucherelor primite. Aflaţi costul minim al călătoriei din oraşul 1 pâna la fiecare oraş.

Date de intrare

Fișierul de intrare vacanta2020.in conține pe prima linie numărul n de oraşe, numărul m de drumuri între aceste oraşe şi numărul k de vouchere, iar pe următoarele m linii câte 3 numere u v c semnificând faptul că între oraşele u şi v există un drum iar costul benzinei pentru parcurgerea lui este c.

Date de ieșire

Fișierul de ieșire vacanta2020.out va conține pe prima linie n numere naturale, reprezentând costurile deplasării de la oraşul 1 la fiecare din cele n oraşe.

Restricții și precizări

• 1 ≤ n ≤ 35.000
• 1 ≤ m ≤ 400.000
• 1 ≤ k ≤ 10
• 1 ≤ u ≠ v ≤ n
• 1 ≤ c ≤ 30.000

Exemplu:

vacanta2020.in

7 11 1
1 2 7
1 3 2
2 3 3
2 4 1
3 4 6
3 5 10
4 5 4
4 6 20
5 6 2
5 7 11
6 7 3

vacanta2020.out

0 0 0 1 2 4 7

Explicație

Un traseu de cost minim de la oraşul 1 la 7 este 1-3-5-6-7, costul acestuia fiind 2+10+2+3=17, însă având un voucher se poate elimina costul drumului 3-5, care are valoarea 10, costul final fiind 17-10=7.

Rezolvare

<syntaxhighlight lang="python3"> import heapq

inf = float('inf')

1. Citirea datelor din fișierul de intrare

with open("vacanta2020.in", "r") as f:

   n, m, k = map(int, f.readline().split())
   G = [[] for _ in range(n + 1)]
   for _ in range(m):
       x, y, c = map(int, f.readline().split())
       G[x].append((y, c))
       G[y].append((x, c))

1. Initializarea distanțelor

d = [[inf] * (k + 1) for _ in range(n + 1)] d[1][0] = 0

1. Folosirea unui heap pentru a implementa algoritmul lui Dijkstra

pq = [(0, 1, 0)] while pq:

   dist, nod, nr_tickete = heapq.heappop(pq)
   if d[nod][nr_tickete] < dist:
       continue
   for nod1, cost in G[nod]:
       # Fără a folosi un bilet
       if d[nod1][nr_tickete] > d[nod][nr_tickete] + cost:
           d[nod1][nr_tickete] = d[nod][nr_tickete] + cost
           heapq.heappush(pq, (d[nod1][nr_tickete], nod1, nr_tickete))
       # Folosind un bilet
       if nr_tickete < k:
           if d[nod1][nr_tickete + 1] > d[nod][nr_tickete]:
               d[nod1][nr_tickete + 1] = d[nod][nr_tickete]
               heapq.heappush(pq, (d[nod1][nr_tickete + 1], nod1, nr_tickete + 1))

1. Scrierea rezultatelor în fișierul de ieșire

with open("vacanta2020.out", "w") as fout:

   for i in range(1, n + 1):
       mini = min(d[i])
       fout.write(str(mini) + ' ')

</syntaxhighlight>