fork download
copy 
  1. //https://u...content-available-to-author-only...o.org/index.php?page=viewproblem2&cpid=717
  2. #include<bits/stdc++.h>
  3. #define int long long
  4. using namespace std;
  5. void usaco(){
  6. 	freopen("visitfj.in","r",stdin);
  7. 	freopen("visitfj.out","w",stdout);
  8. }
  9. int n,t,mx[]={1,-1,0,0},my[]={0,0,1,-1};
  10. bool check(int x,int y){
  11. 	if(x<0||y<0||x>=n||y>=n) return false;
  12. 	return true;
  13. }
  14. signed main() {
  15. 	ios::sync_with_stdio(false); cin.tie(nullptr);
  16. 	usaco();
  17. 	cin>>n>>t;
  18. 	int a[n][n],dis[n][n][3];
  19. 	for(int i=0;i<n;i++){
  20. 		for(int j=0;j<n;j++){
  21. 			cin>>a[i][j];
  22. 			dis[i][j][0]=dis[i][j][1]=dis[i][j][2]=1e18; 
  23. 		}
  24. 	}
  25. 			 //        cost   n   x   y
  26. 	priority_queue<tuple<int,int,int,int>>q;
  27. 	q.push({0,0,0,0}); dis[0][0][0]=0;
  28. 	while(!q.empty()){
  29. 		auto [cost,m,x,y]=q.top(); q.pop();
  30. 		int g=(m+1)%3;
  31. 		cost=-cost;
  32. 		if(cost>dis[x][y][m]) continue;
  33. 		for(int i=0;i<4;i++){
  34. 			if(check(x+mx[i],y+my[i])){
  35. 				if(dis[x+mx[i]][y+my[i]][g]>cost+(g?0:a[x+mx[i]][y+my[i]])+t){
  36. 					dis[x+mx[i]][y+my[i]][g]=cost+(g?0:a[x+mx[i]][y+my[i]])+t;
  37. 					q.push({-dis[x+mx[i]][y+my[i]][g],g,x+mx[i],y+my[i]});
  38. 				}
  39. 			}
  40. 		}
  41. 	}
  42. 	cout<<min({dis[n-1][n-1][0],dis[n-1][n-1][1],dis[n-1][n-1][2]});
  43. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/hJcNIP
language:
C++ (gcc 8.3)
created:
22 days 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!