Weekly Problem #15

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.


Problem Statement

An essential part of circuit design and general system optimization is critical path analysis. On a chip, the critical path represents the longest path any signal would have to travel during execution. In this problem we will be analyzing chip designs to determine their critical path length. The chips in this problem will not contain any cycles, i.e. there exists no path from one component of a chip back to itself.

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.

Definition

Class

#include<string> using namespace std; #include "tvector.h" class Circuits { public: int howLong(const tvector<string>& connects, const tvector<string>& costs) { // fill in code here } };

Constraints

Examples

In each of these examples, quotes ('"'), commas (','), and curly braces ('{' and '}') are included for clarity only. They are never part of the input or output.
  1. connects = {"1 2", "2", ""}
    costs =    {"5 3", "7", ""}
    
    Returns:  12
    
    From above

  2.     
    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.

  3. connects = {"1","2","3","","5","6","7",""}
    costs    = {"2","2","2","","3","3","3",""}
    
    Returns:9
    
    The 0-1-2-3 path costs 6 whereas the 4-5-6-7 path costs 9

  4. 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
    
  5. 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

Owen L. Astrachan
Last modified: Wed Jul 23 10:29:53 EDT 2003