fork(1) download 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. double dis[1005][1005];
  6.  
  7. map< pair< int, int >, int > m;
  8.  
  9. int N, M, K;
  10.  
  11. double min( double a, double b ){
  12.  
  13. 	if( a < b )
  14. 		return a;
  15.  
  16. 	return b;
  17. }
  18.  
  19. int main(){
  20.  
  21. 	cin >> M >> N;
  22.  
  23. 	cin >> K;
  24.  
  25. 	dis[0][0]= 0;
  26.  
  27. 	for( int i= 1; i<= N; ++i )
  28. 		dis[i][0]= 100*i;
  29.  
  30. 	for( int j= 1; j<= M; ++j )
  31. 		dis[0][j]= 100*j;
  32.  
  33. 	for( int i= 0, x,y; i< K; ++i ){
  34.  
  35. 		scanf( "%d%d", &x, &y );
  36. 		m[{y,x}]++; 
  37. 	}
  38.  
  39. 	double shortcut= sqrt(20000);
  40.  
  41. 	for( int i= 1; i<= N; ++i )
  42. 		for( int j= 1; j<= M; ++j ){
  43.  
  44. 			//cout << i << " " << j << "\n\t";
  45.  
  46. 			if( m[{i,j}] > 0 ){
  47.  
  48. 				//cout << dis[i-1][j-1] + sqrt(20000) << " " <<  dis[i-1][j] + 100 << " " << dis[i][j-1] + 100 << endl ;
  49.  
  50. 				dis[i][j]= min( dis[i-1][j-1] + shortcut , min( dis[i-1][j] , dis[i][j-1] ) + 100 ) ;
  51.  
  52. 				m[{i,j}]--;
  53.  
  54. 			}else{
  55.  
  56. 				//cout << dis[i-1][j]+100 << " " << dis[i][j-1] << endl;
  57.  
  58. 				dis[i][j]= min( dis[i-1][j], dis[i][j-1] ) + 100;
  59.  
  60. 			}
  61.  
  62. 		}
  63.  
  64. 	//for( int i =0; i<= N; ++i )
  65. 	//	for( int j= 0; j<= M; ++j )
  66. 	//		cout << dis[i][j] << " \n"[j== M];
  67.  
  68. 	cout << ceil(dis[N][M]) << endl;
  69.  
  70. }
Success #stdin #stdout 0s 11128KB
comments (?)
stdin 
3 2
3
1 1
3 2
1 2
stdout 
383
https://ideone.com/byr7i5
Timus 1119
language:
C++ (gcc 8.3)
created:
9 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!