Vizualizare sursă pentru „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 <code>1</code> până într-un oraş oarecare. El profită şi de oferta guvernului de relansare a turismului, având <code>k</code> 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 <code>1</code> pâna la fiecare oraş.

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

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

= Restricții și precizări =

* <code>1 ≤ n ≤ 35.000</code>
* <code>1 ≤ m ≤ 400.000</code>
* <code>1 ≤ k ≤ 10</code>
* <code>1 ≤ u ≠ v ≤ n</code>
* <code>1 ≤ c ≤ 30.000</code>

= Exemplu: =
<code>vacanta2020.in</code>
 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
<code>vacanta2020.out</code>
 0 0 0 1 2 4 7

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

== Rezolvare ==
<syntaxhighlight lang="python3">
import heapq

inf = float('inf')

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

# Initializarea distanțelor
d = [[inf] * (k + 1) for _ in range(n + 1)]
d[1][0] = 0

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

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