The way home (Codeforces 1801D)
Tags: Greedy, shortest paths

 The famous magician Borya Budini traveled through the country $$$X$$$, which consists of $$$n$$$ cities. However, an accident happened, and he was robbed in the city number $$$1$$$. Now Budini will have a hard way home to the city number $$$n$$$.He's going to get there by plane. In total, there are $$$m$$$ flights in the country, $$$i$$$-th flies from city $$$a_i$$$ to city $$$b_i$$$ and costs $$$s_i$$$ coins. Note that the $$$i$$$-th flight is one-way, so it can't be used to get from city $$$b_i$$$ to city $$$a_i$$$. To use it, Borya must be in the city $$$a_i$$$ and have at least $$$s_i$$$ coins (which he will spend on the flight). After the robbery, he has only $$$p$$$ coins left, but he does not despair! Being in the city $$$i$$$, he can organize performances every day, each performance will bring him $$$w_i$$$ coins. Help the magician find out if he will be able to get home, and what is the minimum number of performances he will have to organize. 

Input: Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 80$$$) – the number of test cases. The description of test cases follows.The first line contains three integers $$$n$$$, $$$m$$$ and $$$p$$$ ($$$2 \le n \le 800$$$, $$$1 \le m \le 3000$$$, $$$0 \le p \le 10^9$$$) — the number of cities, the number of flights and the initial amount of coins.The second line contains $$$n$$$ integers $$$w_1, w_2, \ldots, w_n$$$ $$$(1 \le w_i \le 10^9)$$$ — profit from representations.The following $$$m$$$ lines each contain three integers $$$a_i$$$, $$$b_i$$$ and $$$s_i$$$ ($$$1 \le a_i, b_i \le n$$$, $$$1 \le s_i \le 10^9$$$) — the starting and ending city, and the cost of $$$i$$$-th flight.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$800$$$ and the sum of $$$m$$$ over all test cases does not exceed $$$10000$$$. 

Output: For each test case print a single integer — the minimum number of performances Borya will have to organize to get home, or $$$-1$$$ if it is impossible to do this. 

Note: In the first example, it is optimal for Borya to make $$$4$$$ performances in the first city, having as a result $$$2 + 7 \cdot 4 = 30$$$ coins, and then walk along the route $$$1-3-2-4$$$, spending $$$6+8+11=25$$$ coins.  In the second example, it is optimal for Borya to make $$$15$$$ performances in the first city, fly to $$$3$$$ city, make $$$9$$$ performances there, and then go to $$$4$$$ city. 

Sample Inputs:
4
4 4 2
7 4 3 1
1 2 21
3 2 6
1 3 8
2 4 11
4 4 10
1 2 10 1
1 2 20
2 4 30
1 3 25
3 4 89
4 4 7
5 1 6 2
1 2 5
2 3 10
3 4 50
3 4 70
4 1 2
1 1 1 1
1 3 2

Sample Outputs:
4
24
10
-1

Solution (Python):
import sys
R = sys.stdin.readline
S = lambda : map(int, R().split())
from collections import deque
for _ in range(int(R())):
    (n, m, p) = S()
    w = [0] + [*S()]
    e = [[] for _ in range(n + 1)]
    for _ in range(m):
        (u, v, s) = S()
        e[u] += ((s, v),)
    dd = [{} for _ in range(n + 1)]
    dd[1][w[1]] = (0, -p)
    q = deque([[w[1], 0, p, 1]])
    while q:
        (x, y, z, u) = q.popleft()
        if dd[u][x] < (y, -z):
            continue
        for (s, v) in e[u]:
            nn = [0] * 4
            nn[0] = max(x, w[v])
            if z >= s:
                nn[2] = z - s
                nn[1] = y
            else:
                nn[1] = y + (s - z + x - 1) // x
                nn[2] = z + (s - z + x - 1) // x * x - s
            nn[3] = v
            if nn[0] not in dd[v] or dd[v][nn[0]] > (nn[1], -nn[2]):
                dd[v][nn[0]] = (nn[1], -nn[2])
                q += (nn,)
    print(-1 if not dd[n] else min(dd[n].values())[0])

Solution (Python):
import sys
input = sys.stdin.readline
mod = 998244353
import heapq
from heapq import heappop, heappush

def dijkstra(adj, start):
    inf = 1 << 60
    dist = [inf] * len(adj)
    dist[start] = 0
    q = []
    heapq.heappush(q, (0, start))
    while q:
        (min_dist, v_from) = heapq.heappop(q)
        if min_dist > dist[v_from]:
            continue
        v_tos = adj[v_from]
        for (v_to, cost) in v_tos:
            if min_dist + cost < dist[v_to]:
                dist[v_to] = min_dist + cost
                heapq.heappush(q, (dist[v_to], v_to))
    return dist
for _ in range(int(input())):
    (N, M, P) = map(int, input().split())
    W = [0] + list(map(int, input().split()))
    adj = [[] for _ in range(N + 1)]
    for _ in range(M):
        (a, b, c) = map(int, input().split())
        adj[a].append((b, c))
    dist_list = [[]]
    for v in range(1, N + 1):
        dist = dijkstra(adj, v)
        dist_list.append(dist)
    ans = 10 ** 17
    min_perf = [10 ** 17] * (N + 1)
    min_perf[1] = 0
    max_money = [0] * (N + 1)
    max_money[1] = P
    v_from = 1
    seen = [0] * (N + 1)
    for _ in range(N):
        seen[v_from] = 1
        for v_to in range(1, N + 1):
            if v_to == v_from:
                continue
            d = dist_list[v_from][v_to]
            if d == 1 << 60:
                continue
            if max_money[v_from] >= d:
                perf_new = min_perf[v_from]
                money_new = max_money[v_from] - d
            else:
                perf_num = (d - max_money[v_from] - 1) // W[v_from] + 1
                perf_new = min_perf[v_from] + perf_num
                money_new = max_money[v_from] - d + W[v_from] * perf_num
            if perf_new < min_perf[v_to]:
                min_perf[v_to] = perf_new
                max_money[v_to] = money_new
            elif perf_new == min_perf[v_to]:
                max_money[v_to] = max(max_money[v_to], money_new)
        mi = float('inf')
        v_nxt = -1
        for v_new in range(1, N + 1):
            if seen[v_new]:
                continue
            tmp = min_perf[v_new] * 10 ** 17 - max_money[v_new]
            if tmp < mi:
                mi = tmp
                v_nxt = v_new
        v_from = v_nxt
    if min_perf[N] == 10 ** 17:
        print(-1)
    else:
        print(min_perf[N])

Solution (Python):
import sys
R = sys.stdin.readline
S = lambda : map(int, R().split())
from collections import deque
for _ in range(int(R())):
    (n, m, p) = S()
    w = [0] + [*S()]
    e = [[] for _ in range(n + 1)]
    for _ in range(m):
        (u, v, s) = S()
        e[u] += ((s, v),)
    dd = [{} for _ in range(n + 1)]
    dd[1][w[1]] = (0, -p)
    q = deque([[w[1], 0, p, 1]])
    while q:
        (x, y, z, u) = q.popleft()
        if dd[u][x] < (y, -z):
            continue
        for (s, v) in e[u]:
            nn = [0] * 4
            nn[0] = max(x, w[v])
            if z >= s:
                nn[2] = z - s
                nn[1] = y
            else:
                nn[1] = y + (s - z + x - 1) // x
                nn[2] = z + (s - z + x - 1) // x * x - s
            nn[3] = v
            if nn[0] not in dd[v] or dd[v][nn[0]] > (nn[1], -nn[2]):
                dd[v][nn[0]] = (nn[1], -nn[2])
                q += (nn,)
    print(-1 if not dd[n] else min(dd[n].values())[0])