fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define mod 1000000007
  6. #define sz(c)  (int) c.size()
  7. #define all(c) c.begin(), c.end()
  8. #define tr(container,it) for(__typeof(container.begin()) it = container.begin();it != container.end(); it++)
  9. #define present(s,x) s.find(x) != s.end()
  10. #define cpresent(c,x) find(all(c),x) != c.end()
  11. #define pb push_back
  12. #define mp make_pair
  13. #define ff first
  14. #define ss second
  15. #define rep(i,n) for(int i=0;i<n;i++)
  16. #define dep(i,n) for(int i=n-1;i>=0;i--)
  17. #define repn(i,a,b) for(int i=a; i<b;i++)
  18. #define ini(n) scanf("%d",&n)
  19. #define ind(n,m) scanf("%d %d",&n,&m);
  20. #define ins(n) scanf("%s",n);
  21. #define opi(n) printf("%d",n)
  22. #define ops(n) printf("%s",n)
  23. #define opn printf("\n")
  24. #define opsp printf(" ");
  25. #define opa(n) cout<<n
  26.  
  27. typedef pair<int,int> pi;
  28. typedef vector<pi> vp;
  29. typedef vector<vp> vvp;
  30. typedef vector<int> vi;
  31. typedef unsigned long long int ull;
  32. typedef long long int ll;
  33. typedef vector<ll> vl;
  34. typedef vector< vi > vvi;
  35. typedef priority_queue<int> pq;
  36. typedef priority_queue<int, vi , greater<int> >minpq;
  37. typedef priority_queue<pi,vp,greater<pi> > mpq;
  38.  
  39. pair<ll,ll>  MinRisk(vector<int>&Marked , int idx , int N  , vvi tim , vvi risk , int T , pair<ll,ll> dp[300][300] ){
  40. 	//~ trace3("inside state " , idx, T);
  41. 	//~ if(T < 0){
  42. 		//~ cout<<"current Time is less than  0  so can not be possible return INT_MAX\n" ; 
  43. 		//~ return mp(INT_MAX,INT_MAX);
  44. 	//~ }
  45. 	if(idx == N-1){
  46. 		//~ cout<<"current state is goal state thats why returnign 0 \n" ; 
  47. 		return  {0,0} ; 
  48. 	}
  49. 	if(dp[idx][T].ff != -1)
  50. 		return dp[idx][T] ; 
  51.  
  52. 	ll cost = INT_MAX  ;
  53. 	ll  money=  INT_MAX ; 
  54.  
  55. 	for(int i= 0  ; i<N ; i ++){
  56.  
  57. 		if(i == idx or Marked[i] == 1 or T<tim[idx][i])
  58. 			continue;
  59. 		Marked[i] = 1;
  60. 		//~ cout<<"state ("<<idx<<", "<<T<<") is "<<endl;
  61. 		//~ cout<<"calling State ( "<<i<<","<<T-tim[idx][i]<<")"<<endl;
  62.  
  63. 		pair<ll,ll> calc =  MinRisk(Marked, i ,N, tim ,risk , T-tim[idx][i] , dp);
  64. 		ll tmp = risk[idx][i] + calc.ff;
  65. 		ll tmp2 = tim[idx][i] + calc.ss;
  66. 		//~ trace1(tmp);
  67. 		if(tmp <= cost){
  68. 			cost = tmp ;
  69. 			money = tmp==cost ? min(money,tmp2) : tmp2;
  70. 		}
  71.  
  72.  
  73. 		Marked[i] = 0 ; 
  74. 	}
  75. 	Marked[idx] = 1; 
  76. 	//~ cout<<"State ( "<<idx<<","<<T<<")"<<"returned "<<"optimal cost as "<<cost<<"and optimal time as "<<money<<endl;
  77. 	dp[idx][T] = {cost,money};
  78. 	return  {cost,money}; 
  79. }
  80.  
  81. int main(){
  82. 	//ios_base::sync_with_stdio(false);cin.tie(NULL);
  83. 	int t;
  84. 	cin>>t;
  85. 	while(t--){
  86.  
  87. 		int N,T;
  88. 		cin>>N>>T;
  89. 		vvi risk;
  90. 		vvi tim ; 
  91. 		//~ trace2(N,T);
  92. 		risk.resize(N,vi(N,0));
  93. 		tim.resize(N,vi(N,0));  
  94. 		vector<int>Marked(N,0);
  95. 		for(int i = 0 ; i < N ; i++){
  96. 			for(int j=0; j < N; j++){
  97. 				cin>>tim[i][j] ; 
  98. 			}
  99. 		}
  100. 		for(int i = 0 ; i < N ; i++){
  101. 			for(int j=0; j < N; j++){
  102. 				cin>>risk[i][j] ; 
  103. 			}
  104. 		}
  105. 		pair<ll,ll> dp[300][300]  ; 
  106. 		for(int i=0; i<300 ; i++){
  107. 			for(int j = 0 ; j < 300 ; j++){
  108. 				dp[i][j].ff = -1;
  109. 				dp[i][j].ss = -1;
  110. 			}
  111. 		}
  112. 		//~ cout<<"calling State ( "<<0<<","<<T<<")"<<endl;
  113. 		pair<ll,ll> ans= MinRisk(Marked,0,N,tim, risk , T , dp );
  114. 		if(ans.ff== INT_MAX)
  115. 			cout<<"-1"<<endl;
  116. 		else{
  117. 			cout<<ans.ff<<" "<<ans.ss<<endl;
  118. 		}
  119. 	}
  120.  
  121. }
  122.  
  123.  
  124.  
  125.  
  126.  
  127.  
Success #stdin #stdout 0s 16536KB
comments (?)
stdin
copy 
1
4 10
0 6 2 3
6 0 2 3
3 1 0 2
3 3 2 0
0 2 2 7
2 0 1 2
2 2 0 5
7 2 5 0
stdout
copy 
4 9
https://ideone.com/nwmd0l
language:
C++ (gcc 8.3)
created:
7 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!