CareerCup

#include<iostream>
using namespace std;

void findans(double **graph, int nodes, int time, int start, double p, double answer[])
{
    
    if(time <= 0)
    {
        answer[start] += p;
        return;
    }

    for(int i=1;i<=nodes;i++)
        if(graph[start][i] != 0)
        {
            p *= graph[start][i];
            findans(graph, nodes, time-10 , i , p ,answer);
            p /= graph[start][i];
        }
}

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int nodes,edges,time;
        cin>>nodes>>edges>>time;
        double **graph = new double*[nodes];
        for(int i=1;i<=nodes;i++)
        {
            graph[i] = new double[nodes];
            for(int j=1;j<=nodes;j++)
                graph[i][j] = 0;
        }

        for(int i=0;i<edges;i++)
        {   
            int start, end;
            double prob;
            cin>>start>>end>>prob;
            graph[start][end] = prob;
        }
        double answer[nodes] = {0.0};
        findans(graph, nodes, time, 1, 1.0, answer);
        double final_prob = -1; int final_div = 0;
        for(int i=1;i<=nodes;i++)
        {
            if(answer[i]>final_prob)
            {
                final_prob = answer[i];
                final_div = i;
            }
        }
        cout<<final_div<<" "<<final_prob<<endl;
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
//dt duration to stop in a division
void bfs(vector<pair<int,double> > g[],int n,int dt,int lm)
{
   queue<int> que;
   int division=1;
   double maxprob=0;
   double prob[n];
   bool visited[n];
   for(int i=0;i<n;i++)
    {
        prob[i]=0;
        visited[i]=false;
    }
    que.push(0);
    prob[0]=1;
    visited[0]=true;
    int limit=0;
    while(!que.empty())
    {
        int size=que.size();
        division=1,maxprob=0;
        while(size--)
        {
              int u=que.front();
              que.pop();
              for(int i=0;i<g[u].size();i++)
               {
                   int v=g[u][i].first;
                   double w=g[u][i].second;
                   if(u!=v)
                   {
                   prob[v]+=prob[u]*w;
                   if(maxprob<prob[v])
                     {
                      maxprob=prob[v];
                      division=v+1;
                     }
                      
                   }
                   if(visited[v]==false)
                    {
                     que.push(v);
                     visited[v]=true;
                     }
               }
        }
        
        limit+=dt;
        if(limit>=lm)
         break;
    }
    cout<<std::setprecision(6)<<std::fixed;
    cout<<division<<" "<<maxprob;
   
}
int main()
{
    int t,n,e,ed;
    int sd=10;
    while(cin>>t)
    {
         cin>>n>>e>>ed;
        vector<pair<int,double> > g[n];
        int x,y;
        double p;
        for(int i=0;i<e;i++)
        {
             cin>>x>>y>>p;
            g[x-1].push_back(make_pair(y-1,p));
        }
        cout<<t<<" ";
        bfs(g,n,sd,ed);
        cout<<"\n";
    }
}

can someone tell how probability is 0.774000 after 40 mins ?

#include<iostream>
using namespace std;

int main()
{
	float pm[100][100] = {0};
	float rm[100][100] = {0};
	int nodes, e, t;

	cin >> nodes>>e>>t;
	int x, y;
	for (int i = 0; i < e; i++)
	{
		cin >> x >> y;
		cin >> pm[x-1][y-1];
	}

	rm[0][0] = 1;

	for (int i = 0; i < t/10; i++)  // time
	{
		for (int j = 0; j < nodes ; j++)  // nodes
		{
			if (rm[i][j] > 0)
			{
				for (int k = 0; k < nodes; k++)
				{
					rm[i+1][k]  += rm[i][j]*pm[j][k];
				}				
			}
		}
	}
	float ans = 0;
	int res;
	for (int i = 0; i < nodes; i++)
	{
		if (rm[t / 10][i] > ans)
		{
			ans = rm[t / 10][i];
			res = i;
		}
	}
	cout << res+1 <<" "<< ans << endl;
	return 0;
}

/*
6 10 40
1 2 0.3 1 3 0.7 3 3 0.2 3 4 0.8 2 4 1 4 5 0.9 4 4 0.1 5 6 1 6 3 0.5 6 6 0.5
*/