TopCoder problem "Paths" used in SRM 197 (Division I Level Two)



Problem Statement

    Being second best usually warrants respect and some degree of popularity. Unfortunately, sometimes being second is worse than being last. This phenomenon can be seen in graph theory path-finding algorithms. No one ever seems to pay attention to second best paths! This is unfair and it leaves many almost optimal paths unseen. You wish to change all this by writing an algorithm that detects the second shortest path length in a directed graph, which is not equal to the optimal shortest path length. For the purpose of this problem, a path does not need to have distinct nodes and the length of a path is the sum of all edge weights from the starting node to the ending node. 

Write a class Paths that contains the method secondBest, which takes a String[] graph, int from and int to and returns the length of the second shortest path from the node from to the node to.  graph will contain digits that represent the weights of edges or 'X', which means there is no edge at all.  The jth character of the ith element in graph represents the weight of the edge from node i to node j (i and j are zero-indexed).  If no second best path exists, return -1.

 
Definition
    
Class:Paths
Method:secondBest
Parameters:String[], int, int
Returns:int
Method signature:int secondBest(String[] graph, int from, int to)
(be sure your method is public)
    
 
Notes
-The weight of an edge from node j to node i need not be the same as the weight of an edge from node i to node j.
-Nodes may have an edge pointing to themselves with non-zero weights.
 
Constraints
-graph will contain between 1 and 50 elements, inclusive.
-Each element of graph will contain the same number of characters as the number of elements in graph.
-Each element of graph may contain only digits or 'X'.
-from will be between 0 and the number of elements in graph-1, inclusive.
-to will be between 0 and the number of elements in graph-1, inclusive.
 
Examples
0)
    
{"01111",
 "10111",
 "11011",
 "11101",
 "11110"}
0
0
Returns: 2
In this case, the best path may be no path at all or any number of moves from node 0 back to itself.  In either case, the best path is 0.  The second best path has a length of 2 and can be achieved by moving from node 0 to any other node, and then back to node 0.
1)
    
{"1"}
0
0
Returns: 1
Since the starting node is the ending node, the best path is 0.  The second best path is to move once from node 0 back to itself.
2)
    
{"X1119",
 "1X119",
 "11X19",
 "111X1",
 "9111X"}
0
4
Returns: 3
3)
    
{"X1110",
 "1X111",
 "11111",
 "111X1",
 "0111X"}
0
4
Returns: 2
4)
    
{"X9XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
 "XX9XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
 "X9X9XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
 "X99X9XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
 "X999X9XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
 "X9999X9XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
 "X99999X9XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
 "X999999X9XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
 "X9999999X9XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
 "X99999999X9XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
 "X999999999X9XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
 "X9999999999X9XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
 "X99999999999X9XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
 "X999999999999X9XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
 "X9999999999999X9XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
 "X99999999999999X9XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
 "X999999999999999X9XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
 "X9999999999999999X9XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
 "X99999999999999999X9XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
 "X999999999999999999X9XXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
 "X9999999999999999999X9XXXXXXXXXXXXXXXXXXXXXXXXXXXX",
 "X99999999999999999999X9XXXXXXXXXXXXXXXXXXXXXXXXXXX",
 "X999999999999999999999X9XXXXXXXXXXXXXXXXXXXXXXXXXX",
 "X9999999999999999999999X9XXXXXXXXXXXXXXXXXXXXXXXXX",
 "X99999999999999999999999X9XXXXXXXXXXXXXXXXXXXXXXXX",
 "X999999999999999999999999X9XXXXXXXXXXXXXXXXXXXXXXX",
 "X9999999999999999999999999X9XXXXXXXXXXXXXXXXXXXXXX",
 "X99999999999999999999999999X9XXXXXXXXXXXXXXXXXXXXX",
 "X999999999999999999999999999X9XXXXXXXXXXXXXXXXXXXX",
 "X9999999999999999999999999999X9XXXXXXXXXXXXXXXXXXX",
 "X99999999999999999999999999999X9XXXXXXXXXXXXXXXXXX",
 "X999999999999999999999999999999X9XXXXXXXXXXXXXXXXX",
 "X9999999999999999999999999999999X9XXXXXXXXXXXXXXXX",
 "X99999999999999999999999999999999X9XXXXXXXXXXXXXXX",
 "X999999999999999999999999999999999X9XXXXXXXXXXXXXX",
 "X9999999999999999999999999999999999X9XXXXXXXXXXXXX",
 "X99999999999999999999999999999999999X9XXXXXXXXXXXX",
 "X999999999999999999999999999999999999X9XXXXXXXXXXX",
 "X9999999999999999999999999999999999999X9XXXXXXXXXX",
 "X99999999999999999999999999999999999999X9XXXXXXXXX",
 "X999999999999999999999999999999999999999X9XXXXXXXX",
 "X9999999999999999999999999999999999999999X9XXXXXXX",
 "X99999999999999999999999999999999999999999X9XXXXXX",
 "X999999999999999999999999999999999999999999X9XXXXX",
 "X9999999999999999999999999999999999999999999X9XXXX",
 "X99999999999999999999999999999999999999999999X9XXX",
 "X999999999999999999999999999999999999999999999X9XX",
 "X9999999999999999999999999999999999999999999999X9X",
 "X99999999999999999999999999999999999999999999999X9",
 "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"}
0
49
Returns: 459
5)
    
{"X"}
0
0
Returns: -1
A second best path does not exist in this graph.
Problem url:
 http://www.topcoder.com/stat?c=problem_statement&pm=2431


Problem stats url:
 http://www.topcoder.com/tc?module=ProblemDetail&rd=5072&pm=2431


Writer:
 ValD 

Testers:
 lbackstrom


            , 
            brett1479 

Problem categories:
 Graph Theory