Problem Statement |
| | You're given a weighted, directed graph that satisfies two conditions: each vertex is contained in at most one simple cycle, and for any two vertices u and v, there exists at most one simple path from u to v (see the notes section for definitions).
The graph is described by a String[] graph, where the jth character of the ith element of graph is either '0' if there is no edge from vertex i to j, or a digit between '1' and '9', inclusive, which is the weight of the edge from vertex i to j.
Given such a graph, return the length of the kth shortest path from start to finish. If there are fewer than k paths, you should return -1. Note that all paths of the same length should be counted (see example 3 for clarification). |
| |
Definition |
| | | Class: | ShortPaths | | Method: | getPath | | Parameters: | String[], long, int, int | | Returns: | long | | Method signature: | long getPath(String[] graph, long k, int start, int finish) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | A simple path is an ordered sequence of distinct vertices such that for each vertex in the sequence, there is an edge to the next vertex in the sequence (except for the last vertex). |
| - | A simple cycle is an ordered sequence of vertices such that for each vertex in the sequence, there is an edge to the next vertex in the sequence (except the last vertex). In addition, the sequence must contain no repeated vertices, except for the first and last vertices which must be the same. |
| |
Constraints |
| - | k will be between 1 and 10^12, inclusive. |
| - | The graph represented by graph will satisfy the constraints described in the problem statement. |
| - | graph will contain between 2 and 50 elements, inclusive. |
| - | Each element of graph will contain exactly N characters, where N is the number of elements in graph. |
| - | Each character in graph will be a digit between '0' and '9', inclusive. |
| - | The ith character of the ith element of graph will always be '0'. |
| - | start and finish will be distinct integers between 0 and N-1, inclusive, where N is the number of elements in graph. |
| |
Examples |
| 0) | |
| | {
"0100",
"0020",
"0003",
"4000"
} | 1 | 0 | 2 |
| Returns: 3 | | The direct path between nodes 0 and 2 is 0->1->2. |
|
|
| 1) | |
| | {
"0100",
"0020",
"0003",
"4000"
} | 2 | 0 | 2 |
| Returns: 13 | | The same graph as above, but the second shortest path is 0->1->2->3->0->1->2. |
|
|
| 2) | |
| | {
"011",
"000",
"000"
} | 1 | 1 | 2 |
| Returns: -1 | | There is no path from vertex 1 to vertex 2. |
|
|
| 3) | |
| | {
"010000",
"001010",
"000101",
"000000",
"010000",
"001000"
} | 3 | 0 | 3 |
| Returns: 5 | | The shortest path is of length 3. The next two shortest paths are both of length 5, and since all paths of length 5 must be counted, the third shortest path is of length 5. |
|
|
| 4) | |
| | {
"010000",
"001010",
"000103",
"000000",
"010000",
"002000"
} | 11 | 0 | 3 |
| Returns: 14 | |
|
| 5) | |
| | {
"010000000",
"001002000",
"000100000",
"000010900",
"000000006",
"030000000",
"007000000",
"000040000",
"000000070"
} | 5621 | 0 | 7 |
| Returns: 363 | |
|
| 6) | |
| | {
"09000000000000000000000002000000000000000000000000",
"00900000000000000000000000000000000000000000000000",
"00090000000000000000000000000000000000000000000000",
"00009000000000000000000000000000000000000000000000",
"00000900000000000000000000000000000000000000000000",
"00000090000000000000000000000000000000000000000000",
"00000009000000000000000000000000000000000000000000",
"00000000900000000000000000000000000000000000000000",
"00000000090000000000000000000000000000000000000000",
"00000000009000000000000000000000000000000000000000",
"00000000000900000000000000000000000000000000000000",
"00000000000090000000000000000000000000000000000000",
"00000000000009000000000000000000000000000000000000",
"00000000000000900000000000000000000000000000000000",
"00000000000000090000000000000000000000000000000000",
"00000000000000009000000000000000000000000000000000",
"00000000000000000900000000000000000000000000000000",
"00000000000000000090000000000000000000000000000000",
"00000000000000000009000000000000000000000000000000",
"00000000000000000000900000000000000000000000000000",
"00000000000000000000090000000000000000000000000000",
"00000000000000000000009000000000000000000000000000",
"00000000000000000000000900000000000000000000000000",
"00000000000000000000000090000000000000000000000000",
"40000000000000000000000000000000000000000000000000",
"00000000000000000000000000900000000000000000000000",
"00000000000000000000000000090000000000000000000000",
"00000000000000000000000000009000000000000000000000",
"00000000000000000000000000000900000000000000000000",
"00000000000000000000000000000090000000000000000000",
"00000000000000000000000000000009000000000000000000",
"00000000000000000000000000000000900000000000000000",
"00000000000000000000000000000000090000000000000000",
"00000000000000000000000000000000009000000000000000",
"00000000000000000000000000000000000900000000000000",
"00000000000000000000000000000000000090000000000000",
"00000000000000000000000000000000000009000000000000",
"00000000000000000000000000000000000000900000000000",
"00000000000000000000000000000000000000090000000000",
"00000000000000000000000000000000000000009000000000",
"00000000000000000000000000000000000000000900000000",
"00000000000000000000000000000000000000000090000000",
"00000000000000000000000000000000000000000009000000",
"00000000000000000000000000000000000000000000900000",
"00000000000000000000000000000000000000000000090000",
"00000000000000000000000000000000000000000000009000",
"00000000000000000000000000000000000000000000000900",
"00000000000000000000000000000000000000000000000090",
"00000000000000000000000000000000000000000000000009",
"00000000000000000000000004000000000000000000000000"
} | 10000000000 | 0 | 49 |
| Returns: 31112618 | |
|