Problem: rng (2016 finals)

You're playing a video game that features **N** different areas, numbered from
1 to **N**. There are **M** one-way paths that each connect two areas. The
**i**th path runs from area **Ai** to a different area **Bi**. No pair of
paths directly connect the same pair of areas, and for every area it's
impossible to start at that area and follow a non-empty sequence of paths to
return to that area. In other words, the game's layout is a directed acyclic
graph.

You start in area 1. **K** other distinct areas each contain an item to
collect — the **i**th of these is area **Ii**. As soon as you've visited these
**K** areas at least once each, you win! You'd like to do so as fast as
possible.

At any point in time, if there are no outgoing paths leading away from your
current area, you automatically respawn in area 1 after a delay of **R**
seconds. Otherwise, you get to choose one such path and attempt to follow it.
Unfortunately, this game relies entirely on Random Number Generation to
determine whether or not you'll be successful, regardless of your skill. In
particular, with probability **P**, you'll successfully travel along your
chosen path for **D** seconds, ending up in a new area. On the other hand,
with probability 1 - **P**, you'll instead perish and respawn in area 1 after
a delay of **R** seconds.

What's the minimum expected time for you to collect all **K** items, given
that you play optimally? This is guaranteed to be possible — that is, all
**K** areas that contain items are reachable from area 1. Your output should
have at most 10-6 absolute or relative error.

### Input

Input begins with an integer **T**, the number of times you play the game. For
each time, there is first a line containing the space-separated integers
**N**, **M**, and **K**. The second line contains the space-separated integers
**D** and **R**. The third line contains the real value **P** which is given
with at most 4 decimal places. The fourth line contains the **K** space-
separated integers **I1** to **IK**. Then, **M** lines follow, the **i**th of
which contains the space-separated integers **Ai** and **Bi**.

### Output

For the **i**th time you play the game, print a line containing "Case #**i**:
" followed by the expected time it will take you to collect all of the items
if you play optimally.

### Constraints

1 ≤ **T** ≤ 50  
2 ≤ **N** ≤ 100,000  
1 ≤ **M** ≤ 100,000  
1 ≤ **K** ≤ min(20, **N** \- 1)  
0.5 ≤ **P** ≤ 1.0  
1 ≤ **D**, **R** ≤ 1,000  
1 ≤ **Ai**, **Bi** ≤ **N**  
2 ≤ **Ii** ≤ **N**  

The answer for each game is guaranteed to be less than 1030.

### Explanation of Sample

In the first game, it takes you 10 seconds to reach the only item, and then
you win. There's no chance of failure. The second game is the same as the
first, but now you fail to reach the item with probability 0.5. On average you
will fail once before reaching the item, so you'll incur an average penalty of
3 seconds on top of the 10 seconds it takes you to succeed, for a total of 13
seconds.



Sample input:
5
2 1 1
10 3
1.0
2
1 2
2 1 1
10 3
0.5
2
1 2
7 6 1
1 1000
1.0
7
1 3
3 2
2 7
1 4
4 7
6 5
7 6 4
1 1000
1.0
2 3 4 7
1 3
3 2
2 7
1 4
4 7
6 5
9 10 5
10 8
0.7
5 6 7 8 9
1 2
1 3
1 4
2 5
3 5
3 7
4 6
5 8
5 9
6 8


Sample output:
Case #1: 10.000000000
Case #2: 13.000000000
Case #3: 2.000000000
Case #4: 1004.000000000
Case #5: 168.647230321



Code: // RNG
// Official Solution by Jacob Plachta

#define DEBUG 0

#include <algorithm>
#include <functional>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <complex>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <sstream>
using namespace std;

#define LL long long
#define LD long double
#define PR pair<int,int>

#define Fox(i,n) for (i=0; i<n; i++)
#define Fox1(i,n) for (i=1; i<=n; i++)
#define FoxI(i,a,b) for (i=a; i<=b; i++)
#define FoxR(i,n) for (i=(n)-1; i>=0; i--)
#define FoxR1(i,n) for (i=n; i>0; i--)
#define FoxRI(i,a,b) for (i=b; i>=a; i--)
#define Foxen(i,s) for (i=s.begin(); i!=s.end(); i++)
#define Min(a,b) a=min(a,b)
#define Max(a,b) a=max(a,b)
#define Sz(s) int((s).size())
#define All(s) (s).begin(),(s).end()
#define Fill(s,v) memset(s,v,sizeof(s))
#define pb push_back
#define mp make_pair
#define x first
#define y second

template<typename T> T Abs(T x) { return(x<0 ? -x : x); }
template<typename T> T Sqr(T x) { return(x*x); }
string plural(string s) { return(Sz(s) && s[Sz(s)-1]=='x' ? s+"en" : s+"s"); }

const int INF = (int)1e9;
const LD EPS = 1e-9;
const LD PI = acos(-1.0);

//#if DEBUG
#define GETCHAR getchar
/*#else
#define GETCHAR getchar_unlocked
#endif*/

bool Read(int &x)
{
	char c,r=0,n=0;
	x=0;
		for(;;)
		{
			c=GETCHAR();
				if ((c<0) && (!r))
					return(0);
				if ((c=='-') && (!r))
					n=1;
				else
				if ((c>='0') && (c<='9'))
					x=x*10+c-'0',r=1;
				else
				if (r)
					break;
		}
		if (n)
			x=-x;
	return(1);
}

int main()
{
		if (DEBUG)
			freopen("in.txt","r",stdin);
	int TT,tt;
	int N,M,K,T,R;
	LD P;
	int i,j,k,b;
	LD d,v;
	int S[20];
	static int up[100000],down[100000],dist[100000],dir[20][20];
	static vector<int> con[100000];
	static LD exRN[100001],exNR[100001],exP[100001],exT[100001];
	static LD dyn[1<<20][21];
	queue<int> Q;
	Read(TT);
		Fox1(tt,TT)
		{
			//input
			Read(N),Read(M),Read(K),Read(T),Read(R);
				Fox(i,N)
					con[i].clear();
			cin >> P;
				Fox(i,K)
					Read(S[i]),S[i]--;
				while (M--)
				{
					Read(i),Read(j);
					con[i-1].pb(j-1);
				}
				Fox(i,K)
					dyn[(1<<K)-1][i]=0;
			//dist from start to each item
			Fill(up,-1);
			Q.push(0),up[0]=0;
				while (!Q.empty())
				{
					i=Q.front(),Q.pop();
						Fox(j,Sz(con[i]))
							if (up[k=con[i][j]]<0)
								Q.push(k),up[k]=up[i]+1;
				}
			//dist from each item to other items and to nearest leaf
			Fill(down,-1);
				Fox(b,K)
				{
					Fill(dist,-1);
					Q.push(S[b]),dist[S[b]]=0;
						while (!Q.empty())
						{
							i=Q.front(),Q.pop();
								if ((!Sz(con[i])) && (down[b]<0))
									down[b]=dist[i];
								Fox(j,Sz(con[i]))
									if (dist[k=con[i][j]]<0)
										Q.push(k),dist[k]=dist[i]+1;
						}
						Fox(i,K)
							dir[b][i]=dist[S[i]];
				}
			//expected times for root -> node
			exRN[0]=0;
				Fox1(i,N)
				{
					v=(P*T + (1-P)*(R+exRN[i-1])) / P;
					exRN[i]=exRN[i-1]+v;
				}
			//expected times for node -> root
			exNR[0]=R;
				Fox1(i,N)
					exNR[i]=P*(T + exNR[i-1]) + (1-P)*R;
			//conditional expected times for node -> node
			exP[0]=1;
			exT[0]=0;
				Fox1(i,N)
				{
					exP[i]=exP[i-1]*P;
					exT[i]=exT[i-1] + exP[i-1]*(1-P)*((i-1)*T + R);
				}
			//bitmask DP
				FoxR(b,(1<<K)-1)
				{
					d=-1;
						Fox(i,K)
							if (!(b&(1<<i)))
							{
								v=dyn[b][i]=dyn[b|(1<<i)][i];
								v+=exRN[up[S[i]]];
									if ((d<0) || (d>v))
										d=v;
							}
					dyn[b][K]=d;
						Fox(i,K)
							if (b&(1<<i))
							{
								d=exNR[down[i]]+dyn[b][K];
									Fox(j,K)
										if (!(b&(1<<j)))
											if (dir[i][j]>=0)
											{
												k=dir[i][j];
												v=exP[k]*(k*T + dyn[b][j]) + exT[k] + (1-exP[k])*dyn[b][K];
												Min(d,v);
											}
								dyn[b][i]=d;
							}
				}
			//output
			printf("Case #%d: ",tt);
			cout << fixed << setprecision(9) << dyn[0][K] << endl;
		}
	return(0);
}