RandomDijkstraDiv1
SRM 791 · 2020-10-16 · by laoriu
Problem Statement
Time limit is 3 seconds.
Given is a complete directed graph on N vertices. The vertices are numbered from 0 to N-1. For each pair of distinct vertices u and v, the edge from u to v has a non-negative length dist[u,v].
You are given the edge lengths in the
You wanted to compute the shortest paths from 0 to all other vertices, so you implemented Dijkstra's algorithm. Here is the pseudocode that corresponds to your implementation:
1) S = set of all vertices 2) D[0] = 0 3) for i = 1 to N-1: D[i] = infinity 4) while (S is not empty): 5) find u in S such that D[u] is minimal among all D[i] where i is in S 6) remove u from S 7) for v = 0 to N-1: 8) if D[v] > D[u] + dist[u,v]: 9) D[v] = D[u] + dist[u,v]
The above pseudocode is an actual correct version of Dijkstra's algorithm. When it terminates, each value D[i] is the length of the shortest path from vertex 0 to vertex i.
Your friend then decided to prank you and edited line 5) in the above code to the following one:
5') select u from S uniformly at random
Calculate and return the probability that the modified algorithm will calculate the entire array D correctly.
Notes
- Your return value will be accepted if it has a relative or an absolute error at most 1e-9.
- Note that the cycle in lines 7-9 of the pseudocode iterates over all vertices of the graph, not just over those that are still in the set S.
Constraints
- N will be between 1 and 14, inclusive.
- G will have exactly N*N elements.
- Each element of G will be between 0 and 10^6, inclusive.
- For each u, G[u*N+u] will be 0.
4
{ 0, 1, 1000, 1000, 1000, 0, 1, 1000, 1000, 1000, 0, 1, 1000, 1000, 1000, 0 }
Returns: 0.16666666666666666
A graph on 4 vertices. The edges 0 -> 1, 1 -> 2, and 2 -> 3 each have length 1, all other edges have length 1000 There are multiple ways to get the correct array of distances. The obvious one is to remove the vertices from S in the order 0, 1, 2, 3. A less trivial observation is that removing the vertices in the order 0, 3, 1, 2 does also produce all correct distances in the end.
4
{ 0, 1, 1, 1, 1, 0, 1000, 1000, 1, 1000, 0, 1000, 1, 1000, 1000, 0 }
Returns: 1.0
Sooner or later we will remove vertex 0 from S, and while we process it we will compute the correct distance for all other vertices.
5
{
0, 1000, 1000, 4, 5,
1000, 0, 1000, 1000, 1000,
1000, 2, 0, 1000, 1000,
1000, 1000, 6, 0, 1000,
1000, 7, 1000, 1000, 0
}
Returns: 0.375
13
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
Returns: 1.0
13
{0, 1, 2, 3, 2, 3, 2, 2, 3, 2, 2, 3, 1, 2, 0, 1, 1, 1, 2, 2, 3, 3, 1, 2, 3, 2, 1, 1, 0, 3, 2, 2, 1, 1, 3, 2, 3, 3, 2, 3, 2, 3, 0, 1, 1, 3, 1, 1, 2, 1, 2, 3, 2, 3, 3, 2, 0, 3, 1, 3, 2, 1, 2, 3, 1, 2, 3, 2, 3, 2, 0, 3, 2, 2, 3, 3, 1, 2, 2, 3, 2, 2, 3, 3, 0, 3, 1, 3, 1, 2, 2, 2, 3, 3, 1, 2, 1, 1, 0, 3, 1, 1, 2, 3, 3, 3, 2, 2, 2, 1, 3, 2, 0, 3, 3, 3, 2, 3, 3, 2, 1, 3, 1, 1, 2, 2, 0, 1, 1, 2, 1, 1, 1, 1, 3, 3, 2, 3, 2, 1, 0, 2, 1, 3, 1, 2, 1, 2, 1, 2, 1, 1, 1, 3, 0, 2, 1, 2, 3, 2, 3, 3, 1, 3, 1, 1, 1, 3, 0}
Returns: 0.3333333333333333
Submissions are judged against all 165 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class RandomDijkstraDiv1 with a public method double solve(int N, vector<int> G) · 165 test cases · 2 s / 256 MB per case