RandomDijkstraDiv1 | Topcoder Archive

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 int[] G. For each u and v, dist[u,v] = G[u*N+v].

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] &gt; 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.

Definition

Class:: RandomDijkstraDiv1
Method:: solve
Parameters:: int, int[]
Returns:: double
Method signature:: double solve(int N, int[] G)
(be sure your method is public)

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.

Examples

```
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.

{
      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

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.