Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- # from queue import PriorityQueue
- import heapq
- # Function to calculate the minimum cost
- # required to reach the end of line
- def minCost(N, K, M, a, b):
- flag = 1
- d = {}
- # store index of the station and its respective
- # rate of fuel
- for i in range(M):
- d[a[i]] = b[i]
- """
- Two condition to check:
- 1. If last station is far away such that it cannot
- be reached even if full capacity is filled
- 2. if ith station is far away such that it cannot be reached
- even if full capacity is filled (this is done by checking
- if the difference of two adjacent element exceeds k)
- """
- if K < N-a[i] and i == M-1:
- flag = 0
- break
- if i < M-1 and K < a[i+1] - a[i]:
- flag = 0
- break
- if not flag:
- print(-1)
- return;
- # store station index and cost of fuel and
- # litres of petrol which is being fueled
- # pq=PriorityQueue()
- pq = []
- heapq.heapify(pq)
- cost = 0
- flag = 0
- for i in range(N):
- # check if station is at current index
- if i in d: heapq.heappush(pq, [i, d[i], 0])
- # remove all stations where fuel cannot be pumped
- while len(pq) > 0 and pq[0][2]==K: heapq.heappop(pq)
- # # if no station left to fill fuel
- # not possible to reach end
- if len(pq) == 0:
- flag = 1
- break
- # store best station visited so far
- bestStation = heapq.heappop(pq)
- print(bestStation)
- cost += bestStation[1]
- bestStation[2] += 1
- heapq.heappush(pq, bestStation)
- if flag:
- print(-1)
- return;
- print(cost)
- # Driver code
- if __name__ == "__main__":
- """
- Test case 1:
- N = 10
- K = 3
- M = 4
- a = [0, 1, 4, 6]
- b = [5, 2, 2, 4]
- output: -1
- """
- """
- Test case 2:
- N = 10
- K = 10
- M = 2
- a = [0, 1]
- b = [5, 2]
- output: 23
- """
- N = 10
- K = 5
- M = 3
- a = [0, 3, 5]
- b = [5, 9, 3]
- minCost(N, K, M, a, b)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement