/*
동적 계획법
*/

#include <iostream>
#include <stdio.h>
#include <vector>
#include <string.h>

using namespace std;

double whereisteacher[101][50];// [D][K]에 D날에 K번째 마을의 확률
float realation[50][50];// [D][K] D에서 K로 가는 길의 유무
int manyline[50];
int main()
{
    int i, j, k, l, o;
    int N,D,P,C;//C 테스터 개수, N마을 개수, D D 일 후의 확률 P 감옥 위치
    int H;

    int a;
    double sum = 0;

    scanf("%d",&C);

    for(i=0;i<C;i++){
        scanf("%d %d %d",&N ,&D ,&P);
        for(k=0;k<N;k++){
            for(l=0;l<N;l++){
                scanf("%d",&a);
                if(a==1){
                realation[k][l] = 1;
                manyline[l]++;// l 칸에 연결되어 있는 마을의 갯수
                }
            }
        }
        whereisteacher[0][P] = 1;//탈출전에 감옥 에 있다.
        for(j=1;j<=D;j++){
            for(k=0;k<N;k++){
                for(l=0;l<N;l++){
                    if(realation[l][k] == 1){
                        sum += (whereisteacher[j-1][l] / manyline[l]);// k로 올 확률은 연결되어 있는 마을의 확률에 그 마을에 인접한 마을의 개수로 나눈 값을 모두 더해주면 그 마을에 있을 수 있는 확률이 나옴
                    }
                }
                whereisteacher[j][k] = sum;//
                sum = 0;
            }
        }
        scanf("%d",&H);// 확률을 출력해야할 마을의 개수
        while(H!=0){
            scanf("%d",&o);// 확률 출력
            printf("%.8f ",whereisteacher[D][o]);
            H--;
        }
        printf("\n");
        memset(whereisteacher,0,100*50);
        memset(realation,0,50*50);
        memset(manyline,0,50);
    }

    return 0;
}

16ms 에서 문제가 오답이라고 나온것을 보아 코드가 잘못 짜여진거라고 생각합니다.
문제 기본적 해결 방식은 D 일의 확률은 D-1의 확률로 구할 수 있다를 이용해 동적계획법으로 구상해 보았습니다. 그래서 D 날의 x 라는 마을에 올 확률을 구하려면 D-1 날에서 마을 x와 연결된 모든 마을의 확률을 연결된 각각의 마을을 그 마을이 연결된 마을의 개수로 나누고 더해서 구했습니다.

도움이 필요합니다!