CS3230 Assignment 1 Solution

1 Problem statement
You live in a country with n cities and n−1 bidirectional roads. The transport network of this country can be modelled as a rooted, weighted tree:
• The vertices are labelled 1,2,...,n and each vertex represents a city.
• The edges are labelled 1,2,...,n − 1. Road i connects city i + 1 to its parent p[i]
• Associated with each road i is a weight w[i]. w[i] represents the amount of fuel in liters, required to travel from city i+1 to its parent p[i], or vice versa (the roads are bidirectional, and the fuel required to traverse the road in either direction is w[i] liters).
City i(1 ≤ i ≤ n) contains a petrol station which charges d[i] dollars per liter (different cities can have different prices).
You are currently in your car in city 1 and wish to travel to city n. Your car is currently out of petrol and you wish to find the cheapest way to travel from city 1 to city n (i.e. minimize the total amount of money you pay to all petrol stations). For the purposes of this problem, we will make the following
assumptions:
• There is no limit to the amount of petrol that your car can hold.
• The amount of petrol in your car is not allowed to be negative.
• You are not allowed to sell excess petrol to petrol stations.
• You are allowed to end the journey with an empty petrol tank.
Time complexity requirement: O(n2) for full credit (5 points). Solutions which run in O(n3) will get partial credit (3 points).
2 Input format
The first line of the input consists of a single integer n. The second line of the input consists of n space-separates integers d[1] d[2] ... d[n], representing the cost of petrol in city i. n − 1 lines then follow. The i-th of these line contains two space-separated
integers p[i] and w[i].
3 Output format
Output a single integer, the minimum cost required to travel from city 1 to n, followed by a endline character.
4 Constraints
All test cases will satisfy the following constraints:
• 3 ≤ n ≤ 10000
• 1 ≤ d[i] ≤ 106 (for each 1 ≤ i ≤ n)
• 1 ≤ p[i] ≤ i
• 1 ≤ w[i] ≤ 106
The test cases under the partial task will also satisfy n ≤ 500.
5 Sample input and output
5.1 Sample input 1
3
10 1 1
1 1
1 100
5.2 Sample output 1
111
5.3 Sample input 2
5
14 2 2 11 7
1 10
1 1
1 3
1 1
5.4 Sample output 2
14
6 Submission instructions and grading
Submit your solution to CodeCrunch in either C++ or Java. You need to pass all test cases to get 5 points (or all test cases satisfying n ≤ 500 to get 3 points). The tasks will be labelled full and partial.
• If your final submission to full is correct, you will receive 5 points and your submission to partial will be ignored. If you are confident of your submission to full, you do not need to submit to partial.
• If multiple submissions are made, only the last one will be graded.
No proofs are required.
2.
You are not allowed to share code.