The way home (Codeforces 1802F)
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 io, os
import heapq
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def dijkstra(source, neigh):
    n = len(neigh)
    output = [float('inf')] * n
    heap = []
    heapq.heappush(heap, (0, source))
    while heap:
        ele = heapq.heappop(heap)
        (curr, index) = ele
        if output[index] <= curr:
            continue
        output[index] = curr
        for (nextindex, p) in neigh[index]:
            if output[nextindex] <= curr + p:
                continue
            heapq.heappush(heap, (curr + p, nextindex))
    return output

def main(t):
    (n, m, p) = map(int, input().split())
    profit = list(map(int, input().split()))
    neigh = [[] for _ in range(n)]
    for _ in range(m):
        (u, v, price) = map(int, input().split())
        neigh[u - 1].append((v - 1, price))
    distance = []
    for i in range(n):
        distance.append(dijkstra(i, neigh))
    temp = [[profit[0], 0, p, 0]]
    for i in range(1, n - 1):
        if profit[i] > profit[0]:
            temp.append([profit[i], i, 0, float('inf')])
    temp.append([float('inf'), n - 1, 0, float('inf')])
    temp.sort()
    for i in range(len(temp)):
        for j in range(i + 1, len(temp)):
            d = distance[temp[i][1]][temp[j][1]]
            if d == float('inf'):
                continue
            newtime = (max(0, d - temp[i][2]) - 1) // temp[i][0] + 1 + temp[i][3]
            newrest = (newtime - temp[i][3]) * temp[i][0] + temp[i][2] - d
            if temp[j][3] > newtime:
                temp[j][3] = newtime
                temp[j][2] = newrest
            elif temp[j][3] == newtime and temp[j][2] < newrest:
                temp[j][2] = newrest
    ans = temp[-1][3]
    if ans == float('inf'):
        ans = -1
    print(ans)
T = int(input())
t = 1
while t <= T:
    main(t)
    t += 1

Solution (Python):
from collections import defaultdict as df
from heapq import heappush, heappop

def dijkstra(graph, start, n, cost):
    """"""
    dist = [float('inf')] * n
    dist[start] = 0
    queue = [(0, start)]
    while queue:
        (path_len, v) = heappop(queue)
        if path_len == dist[v]:
            for w in graph[v]:
                edge_len = cost[v][w]
                if edge_len + path_len < dist[w]:
                    dist[w] = edge_len + path_len
                    heappush(queue, (edge_len + path_len, w))
    return dist

def solve():
    t = int(input())
    for _ in range(t):
        (n, m, p) = map(int, input().split())
        profit = list(map(int, input().split()))
        profit[-1] = float('inf')
        profit = [(profit[i], i) for i in range(n)]
        profit.sort()
        graph = df(list)
        cost = df(dict)
        for i in range(m):
            (a, b, s) = map(int, input().split())
            a -= 1
            b -= 1
            graph[a].append(b)
            cost[a][b] = s
    dists = []
    for i in range(n):
        dists.append(dijkstra(graph, i, n, cost))
    start = 0
    for i in range(n):
        if profit[i][1] == 0:
            start = i
            break
    dp = [[float('inf'), 0] for i in range(n)]
    dp
    for i in range(start, n):
        citi = profit[start][1]
        for j in range(i + 1, n):
            c = cost[citi][profit[j][1]]
            (perfom, re) = (0, 0)
            if dp[i][1] < c:
                c -= dp[i][1]
                perfom = c // profit[start][0]
                if perfom * profit[start][0] < c:
                    perfom += 1
                    re = perfom * profit[start][0] - c
            if perfom < dp[j][0]:
                dp[j][0] = perfom
                dp[j][1] = re
            elif perfom == dp[j][0]:
                dp[j][1] = max(re, dp[j][1])
    print(dp[-1][0])
if __name__ == '__main__':
    t = int(input())
    for _ in range(t):
        (n, m, p) = map(int, input().split())
        profit = list(map(int, input().split()))
        profit[-1] = float('inf')
        profit = [(profit[i], i) for i in range(n)]
        profit.sort()
        graph = df(list)
        cost = df(dict)
        for i in range(m):
            (a, b, s) = map(int, input().split())
            a -= 1
            b -= 1
            graph[a].append(b)
            if b in cost[a]:
                cost[a][b] = min(s, cost[a][b])
            else:
                cost[a][b] = s
        dists = []
        for i in range(n):
            dists.append(dijkstra(graph, i, n, cost))
        start = 0
        for i in range(n):
            if profit[i][1] == 0:
                start = i
                break
        dp = [[float('inf'), 0] for i in range(n)]
        (dp[start][0], dp[start][1]) = (0, p)
        for i in range(start, n):
            citi = profit[i][1]
            for j in range(i + 1, n):
                c = dists[citi][profit[j][1]]
                if c >= float('inf'):
                    continue
                if dp[i][1] < c:
                    c -= dp[i][1]
                    perfom = c // profit[i][0]
                    re = 0
                    if perfom * profit[i][0] < c:
                        perfom += 1
                        re = perfom * profit[i][0] - c
                    if perfom + dp[i][0] < dp[j][0]:
                        dp[j][0] = perfom + dp[i][0]
                        dp[j][1] = re
                    elif perfom + dp[i][0] == dp[j][0]:
                        dp[j][1] = max(re, dp[j][1])
                else:
                    re = dp[i][1] - c
                    if dp[i][0] < dp[j][0]:
                        dp[j][0] = dp[i][0]
                        dp[j][1] = re
                    elif dp[i][0] == dp[j][0]:
                        dp[j][1] = max(dp[j][1], re)
        if dp[-1][0] >= float('inf'):
            print(-1)
        else:
            print(dp[-1][0])

Solution (Python):
from collections import defaultdict as df
from heapq import heappush, heappop

def dijkstra(graph, start, n, cost):
    """"""
    dist = [float('inf')] * n
    dist[start] = 0
    queue = [(0, start)]
    while queue:
        (path_len, v) = heappop(queue)
        if path_len == dist[v]:
            for w in graph[v]:
                edge_len = cost[v][w]
                if edge_len + path_len < dist[w]:
                    dist[w] = edge_len + path_len
                    heappush(queue, (edge_len + path_len, w))
    return dist

def solve():
    t = int(input())
    for _ in range(t):
        (n, m, p) = map(int, input().split())
        profit = list(map(int, input().split()))
        profit[-1] = float('inf')
        profit = [(profit[i], i) for i in range(n)]
        profit.sort()
        graph = df(list)
        cost = df(dict)
        for i in range(m):
            (a, b, s) = map(int, input().split())
            a -= 1
            b -= 1
            if b in cost[a]:
                cost[a][b] = min(s, cost[a][b])
            else:
                cost[a][b] = s
            graph[a].append(b)
        dists = []
        for i in range(n):
            dists.append(dijkstra(graph, i, n, cost))
        start = 0
        for i in range(n):
            if profit[i][1] == 0:
                start = i
                break
        dp = [[float('inf'), 0] for i in range(n)]
        (dp[start][0], dp[start][1]) = (0, p)
        for i in range(start, n):
            citi = profit[i][1]
            for j in range(i + 1, n):
                c = dists[citi][profit[j][1]]
                if c >= float('inf'):
                    continue
                if dp[i][1] < c:
                    c -= dp[i][1]
                    perfom = c // profit[i][0]
                    re = 0
                    if perfom * profit[i][0] < c:
                        perfom += 1
                        re = perfom * profit[i][0] - c
                    if perfom + dp[i][0] < dp[j][0]:
                        dp[j][0] = perfom + dp[i][0]
                        dp[j][1] = re
                    elif perfom + dp[i][0] == dp[j][0]:
                        dp[j][1] = max(re, dp[j][1])
                else:
                    re = dp[i][1] - c
                    if dp[i][0] < dp[j][0]:
                        dp[j][0] = dp[i][0]
                        dp[j][1] = re
                    elif dp[i][0] == dp[j][0]:
                        dp[j][1] = max(dp[j][1], re)
        if dp[-1][0] >= float('inf'):
            print(-1)
        else:
            print(dp[-1][0])
if __name__ == '__main__':
    solve()