fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef complex<long double> base;
  6.  
  7. #define pb push_back
  8. #define ll long long
  9. #define ld long double
  10.  
  11. const int maxn=(int)20;
  12. ld sum[maxn],pr[maxn][maxn],a[maxn][maxn];
  13.  
  14. vector<ld> gauss(const vector< vector<ld> > mx)
  15. {	
  16. 	int n=(int)mx.size();
  17.  
  18. 	for(int i=0;i<n;i++)
  19. 	{	
  20. 		memset(a[i],0,sizeof(a[i]));
  21.  
  22. 		for(int j=0;j<n+1;j++)
  23. 		{
  24. 			a[i][j]=mx[i][j];
  25. 		}
  26. 	}
  27.  
  28. 	for(int i=0;i<n;i++)
  29. 	{	
  30. 		int pos=i;
  31.  
  32. 		for(int j=i+1;j<n;j++)
  33. 		{
  34. 			if(fabs(a[j][i])>fabs(a[pos][i]))
  35. 			{
  36. 				pos=j;
  37. 			}
  38. 		}
  39.  
  40. 		for(int j=0;j<n+1;j++)
  41. 		{
  42. 			ld temp=a[i][j];a[i][j]=a[pos][j];
  43.  
  44. 			a[pos][j]=temp;
  45. 		}
  46.  
  47. 		ld now=a[i][i];
  48.  
  49. 		for(int j=0;j<n+1;j++)
  50. 		{
  51. 			a[i][j]/=now;
  52. 		}
  53.  
  54. 		for(int j=0;j<n;j++)
  55. 		{
  56. 			if(j!=i)
  57. 			{
  58. 				ld now=a[j][i];
  59.  
  60. 				for(int k=0;k<n+1;k++)
  61. 				{
  62. 					a[j][k]-=(a[i][k]*now);
  63. 				}
  64. 			}
  65. 		}	
  66. 	}
  67.  
  68. 	vector<ld> ret;
  69.  
  70. 	for(int i=0;i<n;i++)
  71. 	{	
  72. 		ret.pb(a[i][n]);
  73. 	}
  74.  
  75. 	return ret;
  76. }
  77.  
  78. int main()
  79. {
  80. 	int t;cin>>t;
  81.  
  82. 	while(t>0)
  83. 	{
  84. 		int n,s,e;cin>>n>>s>>e;
  85.  
  86. 		s--;e--;
  87.  
  88. 		for(int i=1;i<n;i++)
  89. 		{
  90. 			int u,v,w;
  91.  
  92. 			cin>>u>>v>>w;
  93.  
  94. 			u--;v--;
  95.  
  96. 			sum[u]+=w;
  97.  
  98. 			sum[v]+=w;
  99.  
  100. 			pr[u][v]=w;pr[v][u]=w;
  101. 		}
  102.  
  103. 		if(s==e)
  104. 		{
  105. 			ld res=0;
  106.  
  107. 			cout<<fixed<<setprecision(5)<<res<<endl;
  108. 		}
  109.  
  110. 		else
  111. 		{
  112. 			vector< vector<ld> > p,id;
  113.  
  114. 			for(int i=0;i<n;i++)
  115. 			{
  116. 				vector<ld> curr;curr.resize(n,0.0);
  117.  
  118. 				curr[i]=1.0;
  119.  
  120. 				id.pb(curr);
  121. 			}
  122.  
  123. 			for(int i=0;i<n;i++)
  124. 			{
  125. 				if(i!=e)
  126. 				{
  127. 					vector<ld> row_prob;
  128.  
  129. 					for(int j=0;j<n;j++)
  130. 					{
  131. 						row_prob.pb(pr[i][j]/sum[i]);
  132. 					}
  133.  
  134. 					p.pb(row_prob);
  135. 				}
  136.  
  137. 				else
  138. 				{
  139. 					vector<ld> zo;zo.resize(n,0.0);zo[e]=1.0;
  140.  
  141. 					p.pb(zo);
  142. 				}
  143. 			}
  144.  
  145. 			vector< vector<ld> > m;
  146.  
  147. 			for(int i=0;i<n;i++)
  148. 			{
  149. 				vector<ld> v;
  150.  
  151. 				for(int j=0;j<n;j++)
  152. 				{
  153. 					ld curr=id[i][j]-p[i][j];
  154.  
  155. 					v.pb(curr);
  156. 				}
  157.  
  158. 				m.pb(v);
  159. 			}
  160.  
  161. 			vector< vector<ld> > mx;
  162.  
  163. 			for(int i=0;i<n;i++)
  164. 			{
  165. 				if(i!=e)
  166. 				{
  167. 					vector<ld> zz;
  168.  
  169. 					for(int j=0;j<n;j++)
  170. 					{
  171. 						if(j!=e)
  172. 						{
  173. 							zz.pb(m[i][j]);
  174. 						}
  175. 					}
  176.  
  177. 					zz.pb(1.0);mx.pb(zz);
  178. 				}
  179. 			}
  180.  
  181. 			vector<ld> ans=gauss(mx);int idx=(s<e?s:s-1);
  182.  
  183. 			cout<<fixed<<setprecision(5)<<ans[idx]<<endl;
  184. 		}
  185.  
  186. 		for(int i=0;i<n;i++)
  187. 		{	
  188. 			sum[i]=0;
  189.  
  190. 			for(int j=0;j<n;j++)
  191. 			{
  192. 				pr[i][j]=0;
  193. 			}
  194. 		}
  195.  
  196. 		t--;
  197. 	}
  198.  
  199. 	return 0;
  200. }
  201.  
  202.  
  203.  
  204.  
Success #stdin #stdout 0s 4340KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/gKvrbY
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!