← 返回 amazon 的题目列表Minimum Cost to Visit Requested Hubs in a Circular Drone Route
类型：online_judge
Problem Statement
There are n drone hubs numbered from 1 to n, arranged in a circle:
hub 1 is adjacent to hub 2;
hub 2 is adjacent to hub 3;
...
hub n - 1 is adjacent to hub n;
hub n is adjacent to hub 1.
You are given:
requestedHubs: a list of hubs that must be visited in order;
transitionTime: an array of length n, where transitionTime[i - 1] is the cost of leaving hub i and moving to either adjacent hub.
The drone can only move to an adjacent hub at each step. For every pair of consecutive hubs in requestedHubs, the drone may move clockwise or counterclockwise and should choose the cheaper direction.
Compute the minimum total cost to visit all hubs in requestedHubs in order.
Assume the drone starts at requestedHubs[0], so there is no cost to reach the first requested hub.
Be careful: the hubs form a cycle, so hub n and hub 1 are adjacent.
Input Format
n
m
requestedHubs[0] requestedHubs[1] ... requestedHubs[m-1]
transitionTime[0] transitionTime[1] ... transitionTime[n-1]
Output Format
Print one integer: the minimum total cost.
Constraints
1 <= n <= 2 * 10^5
1 <= m <= 2 * 10^5
1 <= requestedHubs[i] <= n
0 <= transitionTime[i] <= 10^9
The answer may exceed 32-bit integer range.
Example 1
Input:
5
3
1 3 5
1 2 3 4 5
Output:
9
Explanation:
From hub 1 to hub 3:
clockwise: 1 -> 2 -> 3, cost 1 + 2 = 3;
counterclockwise: 1 -> 5 -> 4 -> 3, cost 1 + 5 + 4 = 10;
choose 3.
From hub 3 to hub 5:
clockwise: 3 -> 4 -> 5, cost 3 + 4 = 7;
counterclockwise: 3 -> 2 -> 1 -> 5, cost 3 + 2 + 1 = 6;
choose 6.
Total cost is 3 + 6 = 9.
Example 2
Input:
4
4
1 4 2 1
10 1 1 1
Output:
13
Explanation:
1 -> 4: directly counterclockwise, cost 10;
4 -> 2: clockwise costs 1 + 10 = 11, counterclockwise costs 1 + 1 = 2, choose 2;
2 -> 1: counterclockwise, cost 1;
total cost is 10 + 2 + 1 = 13.
Example
Input
5
3
1 3 5
1 2 3 4 5
Output
9