Connection Status:
Competition Arena > Paths

Paths

SRM 197 · 2004-06-02 · by ValD

SRM 197 · 2004-06-02 · by ValD · Graph Theory
Class Name: Paths
Return Type: int
Method Name: secondBest
Arg Types: (vector<string>, int, int)
Problem Statement

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.

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)
{"X1119",
 "1X111",
 "11111",
 "111X1",
 "9111X"}
0
4
Returns: 3
4)
{"X1110",
 "1X111",
 "11111",
 "111X1",
 "0111X"}
0
4
Returns: 2
6)
{"6X4XX50392",
 "95979050X4",
 "703X7X4218",
 "6602806624",
 "9828648374",
 "259507367X",
 "8810887807",
 "002378X847",
 "446X754724",
 "1128726659"}
3
3
Returns: 1

Random test case.

7)
{"19999",
 "99999",
 "99999",
 "99999",
 "99999"}
0
4
Returns: 10

The only way to get the 2nd best path is to move once from node 0 back to itself and then move directly to node 4.

9)
{"01XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
 "X01XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
 "XX01XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
 "XXX01XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
 "XXXX01XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
 "XXXXX01XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
 "XXXXXX01XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
 "XXXXXXX01XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
 "XXXXXXXX01XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
 "XXXXXXXXX01XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
 "XXXXXXXXXX01XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
 "XXXXXXXXXXX01XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
 "XXXXXXXXXXXX01XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
 "XXXXXXXXXXXXX01XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
 "XXXXXXXXXXXXXX01XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
 "XXXXXXXXXXXXXXX01XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
 "XXXXXXXXXXXXXXXX01XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
 "XXXXXXXXXXXXXXXXX01XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
 "XXXXXXXXXXXXXXXXXX01XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
 "XXXXXXXXXXXXXXXXXXX01XXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
 "XXXXXXXXXXXXXXXXXXXX01XXXXXXXXXXXXXXXXXXXXXXXXXXXX",
 "XXXXXXXXXXXXXXXXXXXXX01XXXXXXXXXXXXXXXXXXXXXXXXXXX",
 "XXXXXXXXXXXXXXXXXXXXXX01XXXXXXXXXXXXXXXXXXXXXXXXXX",
 "XXXXXXXXXXXXXXXXXXXXXXX01XXXXXXXXXXXXXXXXXXXXXXXXX",
 "XXXXXXXXXXXXXXXXXXXXXXXX01XXXXXXXXXXXXXXXXXXXXXXXX",
 "XXXXXXXXXXXXXXXXXXXXXXXXX01XXXXXXXXXXXXXXXXXXXXXXX",
 "XXXXXXXXXXXXXXXXXXXXXXXXXX01XXXXXXXXXXXXXXXXXXXXXX",
 "XXXXXXXXXXXXXXXXXXXXXXXXXXX01XXXXXXXXXXXXXXXXXXXXX",
 "XXXXXXXXXXXXXXXXXXXXXXXXXXXX01XXXXXXXXXXXXXXXXXXXX",
 "XXXXXXXXXXXXXXXXXXXXXXXXXXXXX01XXXXXXXXXXXXXXXXXXX",
 "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX01XXXXXXXXXXXXXXXXXX",
 "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX01XXXXXXXXXXXXXXXXX",
 "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX01XXXXXXXXXXXXXXXX",
 "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX01XXXXXXXXXXXXXXX",
 "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX01XXXXXXXXXXXXXX",
 "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX01XXXXXXXXXXXXX",
 "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX01XXXXXXXXXXXX",
 "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX01XXXXXXXXXXX",
 "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX01XXXXXXXXXX",
 "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX01XXXXXXXXX",
 "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX01XXXXXXXX",
 "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX01XXXXXXX",
 "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX01XXXXXX",
 "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX01XXXXX",
 "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX01XXXX",
 "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX01XXX",
 "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX01XX",
 "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX01X",
 "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX01",
 "1XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX0"}
2
1
Returns: 99

A ring of 50 nodes, where every node also points back to itself with a weight of zero. The second best path is to go around the ring twice.

10)
{"X"}
0
0
Returns: -1

A second best path does not exist in this graph.

11)
{"09XXXXXXXX",
 "0099999999",
 "0009999999",
 "0000999999",
 "0000099999",
 "0000009999",
 "0000000999",
 "0000000099",
 "0000000009",
 "0000000000"}
0
9
Returns: 27

Cycles all over the place.

12)
{"0123456789",
 "9012345678",
 "8901234567",
 "7890123456",
 "6789012345",
 "5678901234",
 "4567890123",
 "3456789012",
 "2345678901",
 "1234567890"}
0
9
Returns: 19

At least 10 different optimal paths.

16)
{"00000000000000000000000000000000000000000000000000",
 "00000000000000000000000000000000000000000000000000",
 "00000000000000000000000000000000000000000000000000",
 "00000000000000000000000000000000000000000000000000",
 "00000000000000000000000000000000000000000000000000",
 "00000000000000000000000000000000000000000000000000",
 "00000000000000000000000000000000000000000000000000",
 "00000000000000000000000000000000000000000000000000",
 "00000000000000000000000000000000000000000000000000",
 "00000000000000000000000000000000000000000000000000",
 "00000000000000000000000000000000000000000000000000",
 "00000000000000000000000000000000000000000000000000",
 "00000000000000000000000000000000000000000000000000",
 "00000000000000000000000000000000000000000000000000",
 "00000000000000000000000000000000000000000000000000",
 "00000000000000000000000000000000000000000000000000",
 "00000000000000000000000000000000000000000000000000",
 "00000000000000000000000000000000000000000000000000",
 "00000000000000000000000000000000000000000000000000",
 "00000000000000000000000000000000000000000000000000",
 "00000000000000000000000000000000000000000000000000",
 "00000000000000000000000000000000000000000000000000",
 "00000000000000000000000000000000000000000000000000",
 "00000000000000000000000000000000000000000000000000",
 "00000000000000000000000000000000000000000000000000",
 "00000000000000000000000000000000000000000000000000",
 "00000000000000000000000000000000000000000000000000",
 "00000000000000000000000000000000000000000000000000",
 "00000000000000000000000000000000000000000000000000",
 "00000000000000000000000000000000000000000000000000",
 "00000000000000000000000000000000000000000000000000",
 "00000000000000000000000000000000000000000000000000",
 "00000000000000000000000000000000000000000000000000",
 "00000000000000000000000000000000000000000000000000",
 "00000000000000000000000000000000000000000000000000",
 "00000000000000000000000000000000000000000000000000",
 "00000000000000000000000000000000000000000000000000",
 "00000000000000000000000000000000000000000000000000",
 "00000000000000000000000000000000000000000000000000",
 "00000000000000000000000000000000000000000000000000",
 "00000000000000000000000000000000000000000000000000",
 "00000000000000000000000000000000000000000000000000",
 "00000000000000000000000000000000000000000000000000",
 "00000000000000000000000000000000000000000000000000",
 "00000000000000000000000000000000000000000000000000",
 "00000000000000000000000000000000000000000000000000",
 "00000000000000000000000000000000000000000000000000",
 "00000000000000000000000000000000000000000000000000",
 "00000000000000000000000000000000000000000000000000",
 "00000000000000000000000000000000000000000000000000"}
0
49
Returns: -1

Only optimal paths here.

Submissions are judged against all 26 archived test cases, of which 12 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Paths with a public method int secondBest(vector<string> graph, int from, int to) · 26 test cases · 2 s / 256 MB per case

Submitting as anonymous