ShortPaths
SRM 406 · 2008-06-18 · by eleusive
SRM 406 · 2008-06-18 · by eleusive · Dynamic Programming, Graph Theory, Math, Search
Problem Statement
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).
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).
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
7)
{
"0100",
"0020",
"0003",
"0400"
}
2
0
1
Returns: 10
Finish is part of a cycle 1
8)
{
"0100",
"0020",
"0003",
"0400"
}
5
0
2
Returns: 39
Finish in a cycle 2
9)
{
"0100",
"0020",
"0003",
"0400"
}
10
0
3
Returns: 87
Finish part of a cycle 3
10)
{
"0100",
"0023",
"0000",
"4000"
}
2
0
2
Returns: 11
Start part of a cycle 1
11)
{
"0100",
"0023",
"0000",
"4000"
}
5
1
2
Returns: 34
Start part of a cycle 2
12)
{
"0100",
"0023",
"0000",
"4000"
}
10
3
2
Returns: 79
Start part of a cycle 3
13)
{
"0100",
"0020",
"0003",
"4000"
}
2
0
2
Returns: 13
start, finish in the same cycle 1
14)
{
"0100",
"0020",
"0003",
"4000"
}
5
2
0
Returns: 47
start, finish in the same cycle 2
15)
{
"0100",
"0020",
"0003",
"4000"
}
10
0
3
Returns: 96
start, finish in the same cycle 3
16)
{
"0100",
"0020",
"0003",
"4000"
}
50
1
0
Returns: 499
start, finish in the same cycle 4
17)
{
"0100",
"0000",
"0001",
"0000"
}
2
0
3
Returns: -1
start, finish in seperate components
18)
{
"00",
"10"
}
1
0
1
Returns: -1
path from finish->start, but not start->finish
19)
{
"01100",
"00000",
"00010",
"00001",
"00100"
}
2
0
1
Returns: -1
make sure we discard cycles reachable from start that don't reach finish
20)
{
"01000",
"00000",
"01001",
"00100",
"00010"
}
2
0
1
Returns: -1
make sure we discard cycles that reach finish but aren't reachable from start
21)
{
"01000",
"00000",
"00010",
"00001",
"00100"
}
2
0
1
Returns: -1
make sure we discard cycles in other components
22)
{
"01",
"00"
}
10
0
1
Returns: -1
simple case with no cycles
102)
{
"000",
"001",
"000"
}
1
0
1
Returns: -1
isolated start vertex
103)
{
"010",
"000",
"000"
}
1
0
2
Returns: -1
isolated end vertex
104)
{
"000",
"000",
"000"
}
1
0
1
Returns: -1
empty graph
105)
{
"01500000000000000000000000000000000000000000000000",
"10000000000000000000000000000000000000000000000000",
"00013000000000000000000000000000000000000000000000",
"00100000000000000000000000000000000000000000000000",
"00000120000000000000000000000000000000000000000000",
"00001000000000000000000000000000000000000000000000",
"00000001200000000000000000000000000000000000000000",
"00000010000000000000000000000000000000000000000000",
"00000000015000000000000000000000000000000000000000",
"00000000100000000000000000000000000000000000000000",
"00000000000130000000000000000000000000000000000000",
"00000000001000000000000000000000000000000000000000",
"00000000000001800000000000000000000000000000000000",
"00000000000010000000000000000000000000000000000000",
"00000000000000013000000000000000000000000000000000",
"00000000000000100000000000000000000000000000000000",
"00000000000000000180000000000000000000000000000000",
"00000000000000001000000000000000000000000000000000",
"00000000000000000001100000000000000000000000000000",
"00000000000000000010000000000000000000000000000000",
"00000000000000000000014000000000000000000000000000",
"00000000000000000000100000000000000000000000000000",
"00000000000000000000000160000000000000000000000000",
"00000000000000000000001000000000000000000000000000",
"00000000000000000000000001700000000000000000000000",
"00000000000000000000000010000000000000000000000000",
"00000000000000000000000000019000000000000000000000",
"00000000000000000000000000100000000000000000000000",
"00000000000000000000000000000130000000000000000000",
"00000000000000000000000000001000000000000000000000",
"00000000000000000000000000000001300000000000000000",
"00000000000000000000000000000010000000000000000000",
"00000000000000000000000000000000017000000000000000",
"00000000000000000000000000000000100000000000000000",
"00000000000000000000000000000000000190000000000000",
"00000000000000000000000000000000001000000000000000",
"00000000000000000000000000000000000001900000000000",
"00000000000000000000000000000000000010000000000000",
"00000000000000000000000000000000000000018000000000",
"00000000000000000000000000000000000000100000000000",
"00000000000000000000000000000000000000000190000000",
"00000000000000000000000000000000000000001000000000",
"00000000000000000000000000000000000000000001700000",
"00000000000000000000000000000000000000000010000000",
"00000000000000000000000000000000000000000000019000",
"00000000000000000000000000000000000000000000100000",
"00000000000000000000000000000000000000000000000170",
"00000000000000000000000000000000000000000000001000",
"00000000000000000000000000000000000000000000000001",
"00000000000000000000000000000000000000000000000010"
}
1000000000000
0
49
Returns: 176
maximum # of cycles
106)
{
"0100",
"0010",
"1000",
"0000"
}
1
0
3
Returns: -1
start in cycle, can't reach finish
107)
{
"0000",
"0010",
"0001",
"0100"
}
1
0
1
Returns: -1
end in cycle, not reachable from start
Submissions are judged against all 155 archived test cases, of which 27 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class ShortPaths with a public method long long getPath(vector<string> graph, long long k, int start, int finish) · 155 test cases · 2 s / 256 MB per case