## Samsung Interview Question

Backend Developers**Country:**India

**Interview Type:**Written Test

```
#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";
}
}
```

- Samurai July 26, 2019