Given a tvector<string>
connects representing the
wiring scheme, and a
vector<string>
costs representing the cost of each
connection, your method will return the size of the most costly path
between any 2 components on the chip. In other words, you are to find
the longest path in a directed, acyclic graph. Element j of connects
will list the components of the chip that can be reached directly from
the jth component (0-based). Element j of costs will list the costs of
each connection mentioned in the jth element of connects. As mentioned
above, the chip will not contain any cyclic paths.
For example:
connects = {"1 2", "2", ""} costs = {"5 3", "7", ""}In this example, component 0 connects to components 1 and 2 with costs 5 and 3 respectively. Component 1 connects to component 2 with a cost of 7. All connections mentioned are directed. This means a connection from component i to component j does not imply a connection from component j to component i. Since we are looking for the longest path between any 2 components, your method would return 12.
tvector<string>
, tvector<string>
,
connects = {"1 2", "2", ""} costs = {"5 3", "7", ""} Returns: 12From above
connects = {"1 2 3 4 5","2 3 4 5","3 4 5","4 5","5",""} costs = {"2 2 2 2 2","2 2 2 2","2 2 2","2 2","2",""} Returns: 10
The longest path goes from 0-1-2-3-4-5 for a cost of 10.
connects = {"1","2","3","","5","6","7",""} costs = {"2","2","2","","3","3","3",""} Returns:9The 0-1-2-3 path costs 6 whereas the 4-5-6-7 path costs 9
connects = {"","2 3 5","4 5","5 6","7","7 8","8 9","10", "10 11 12","11","12","12",""} costs = {"","3 2 9","2 4","6 9","3","1 2","1 2","5", "5 6 9","2","5","3",""} Returns: 22
connects = {"","2 3","3 4 5","4 6","5 6","7","5 7",""} costs = {"","30 50","19 6 40","12 10","35 23","8","11 20",""}Returns: 105