HDU Walk（確率DP）

HDU Walk（確率DP）：http://acm.hdu.edu.cn/showproblem.php?pid=5001
タイトルの説明:
Time Limit：30000/15000 MS（Java/Others）    メモリLimit：65536/65536 K（Java/Others）Total Submission（s）：996    Acceepted Submission(s)：634 Special Jundge
Problem Description
I used to think I could be anything、but now I know I couldn't do anything.So I started trveling.
The nation looks like a connected bidirection al graph，an d I am randmly walking on it.It means when I am at node i，I will travel to an adjacenode with the same.I will pick the next step.Inoting that I may go through some nodes multiple times.
If I miss some sights a t a node，it will make me unhappy.So I wonder for each node，what is the probability that my path doesn't contain it.
 
Input
The first line contains an integer T，denoting the number of the test cases.
For each test case，the first line contains 3 integers n，m a n d d，denoting the number of vertices，the number of edges and the number of steps rectively.The n m lines follows，eas conining the and indentinage
T<=20,n<=50，n-1<=m*(n-1)/2，1<=d==10000.The re isのself-loops or multiple edges in the graph，and the graph is connected.The nodes are indexed from 1.
 
Output
For each test cases、output n lineas、the i-th line containing the desired probability for the i-th node.
Your answer will be accepted if its absoute error doesn't exceed 1 e-5.
 
Sample Input

   
   
   
   

    
    
    
    2
5 10 100
1 2
2 3
3 4
4 5
1 5
2 4
3 5
2 5
1 4
1 3
10 10 10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
4 9
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.6993317967
0.5864284952
0.4440860821
0.2275896991
0.4294074591
0.4851048742
0.4896018842
0.4525044250
0.3406567483
0.6421630037
   
   
   
   
   
   
   
   


   
   
   
   

タイトルの大意:
n個のノードでは、m個の辺の無方向図において、各頂点を起点とする確率は等しい。d歩を経過した後、この点を通過しない確率はいくらであるかを求める。
テーマ解析:
このノードを通過しない確率は、ノードの図の中でdステップを除いて他の頂点に移動したものと同じです。
この点iに到達させないため、点iに到達しない確率は他の頂点に到達する確率と、この点を求めなくても良い。
コードの実装:

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>

using namespace std;
#define maxn 55
#define maxstep 10005
vector<int> V[maxn];
double dp[maxstep][maxn];

int main()
{
    int T;
    int n,m,d;
    scanf("%d",&T);
    while(T--)
    {
        int a,b;
        scanf("%d%d%d",&n,&m,&d);
        for( int i=1; i<=n; i++)
        {
            V[i].clear();
        }
        for( int i=1; i<=m; i++)
        {
            scanf("%d%d",&a,&b);
            V[a].push_back(b);
            V[b].push_back(a);
        }
        for(int i=1; i<=n; i++)
        {
            dp[0][i]=1.0/n;
        }
        for(int i=1; i<=n; i++)
        {
            //memset(dp,0,sizeof(dp));
            for(int j=1; j<=d; j++)
            {
                for(int k=1; k<=n; k++)
                {
                    if(k==i)
                        continue;
                    dp[j][k]=0;
                    for(int q=0; q<V[k].size(); q++)
                    {
                        if(V[k][q]==i) continue;
                        else dp[j][k]+=dp[j-1][V[k][q]]*(1.0/V[k].size());
                    }
                }
            }
            double ans=0;
            for(int j=1; j<=n; j++)
            {
                if(j==i)
                    continue;
                else ans+=dp[d][j];
            }
                printf("%.10lf
",ans);
        }
    }
    return 0;
}