← 返回 amazon 的题目列表Minimum Travel Time for Drone Deliveries on a Circular Hub Route
类型：online_judge
Problem: Minimum Travel Time for Drone Deliveries on a Circular Hub Route
There are n delivery hubs arranged in a circle, numbered from 0 to n - 1. You are given an array distance, where distance[i] is the travel time from hub i to hub (i + 1) % n in the clockwise direction.
A drone starts at hub 0 and must visit the hubs in the given deliveries list in order. Between any two hubs, the drone may travel either clockwise or counterclockwise. Return the minimum total travel time needed to complete all deliveries.
Input Format
The first line contains two integers n and m, the number of hubs and the number of deliveries.
The second line contains n integers: distance[0], distance[1], ..., distance[n-1].
The third line contains m integers: deliveries[0], deliveries[1], ..., deliveries[m-1], the hubs to visit in order.
The drone starts at hub 0.
Output Format
Print one integer: the minimum total travel time.
Constraints
2 <= n <= 10^5
0 <= m <= 10^5
1 <= distance[i] <= 10^9
0 <= deliveries[i] < n
The answer may exceed the 32-bit integer range.
Example 1
Input:
4 3
1 2 3 4
1 2 3
Output:
6
Explanation:
0 -> 1: minimum time is 1
1 -> 2: minimum time is 2
2 -> 3: minimum time is 3
Total time is 6
Example 2
Input:
4 1
1 2 3 4
3
Output:
4
Explanation: From 0 to 3, going counterclockwise across edge 3 -> 0 takes 4, which is shorter than the clockwise distance 1 + 2 + 3 = 6.
Example
Input
4 3
1 2 3 4
1 2 3
Output
6