fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. #define MAX 100;
  4. const unsigned int M = 1000000007;
  5. using namespace std;
  6. int fopt=M,b[1000],a[1000],can=0,cmin,Fopt[1000];
  7. void inPut(int A[15][15],int &n){
  8. 	cin>>n;
  9. 	for(int i=1;i<=n;i++)
  10. 		for(int j=1;j<=n;j++)
  11. 			cin>>A[i][j];
  12. }
  13. int MinAr(int A[15][15],int n){
  14. 	int min=M;
  15. 	for(int i=1;i<=n;i++)
  16. 		for(int j=1;j<n;j++)
  17. 			if(A[i][j]<min && i!=j) min=A[i][j];
  18. 	return min;
  19. }
  20. void Init(int A[15][15],int n){
  21. 	for(int i=0;i<=n;i++)
  22. 		b[i]=1;
  23. 	a[1]=1;
  24. 	cmin=MinAr(A,n);
  25. }
  26. void Update(int A[15][15],int n){
  27. 	if(can+A[1][a[n]]<fopt){
  28. 		fopt=can+A[1][a[n]];
  29. 		for(int i=1;i<=n;i++)
  30. 			Fopt[i]=a[i];
  31. 	} 
  32. }
  33. void Result(int n){
  34. //	for(int i=1;i<=n;i++)
  35. //		cout<<a[i]<<"->";
  36. 	cout<<fopt<<endl;
  37. }
  38. void Try(int i,int n,int A[15][15]){
  39. 	for(int j=2;j<=n;j++){
  40. 		if(b[j]){
  41. 			a[i]=j;
  42. 			can+=A[a[i-1]][a[i]];
  43. 			b[j]=0;
  44. 			if(i==n) Update(A,n);
  45. 			else if(can+(n-i+1)*cmin<fopt)
  46. 				Try(i+1,n,A);
  47. 			b[j]=1;
  48. 			can-=A[a[i-1]][i];
  49. 		}
  50. 	}
  51. }
  52. main(){
  53. 	int n,A[15][15];
  54. 	inPut(A,n);
  55. 	Init(A,n);
  56. 	Try(2,n,A);
  57. 	Result(n);
  58. }
  59.  
Success #stdin #stdout 0s 4532KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1000000007
https://ideone.com/CMemTb
language:
C++ (gcc 8.3)
created:
6 years ago
visibility:
public

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!