CS3230 programming assignment 1
Due: 6 Nov 23:59
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 + 1]
• 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(n
2
) for full credit (5 points). Solutions
which run in O(n
3
) will get partial credit (3 points).
1
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 + 1] 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
2
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 your submission to full is incorrect, or you did not submit to full, then
your solution to partial will be graded, in which you may receive 3 points
if your solution to partial is correct.
• If multiple submissions are made, only the last one will be graded.
No proofs are required.
7 Collaboration policy
You may discuss the problems with your classmates, though you should write
up your solutions on your own. Please note the names of your collaborators in
your submission. You may want to refer to the plagiarism policy from Lecture
2.
You are not allowed to share code.
3
Problem Statement
