题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=4992
dis[i][j][k]表示在第i行第j列，已经走了k步(0<=k<3)
然后无脑跑个SPFA就好了
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
#include<bits/stdc++.h> #define N 110 #define inf INT_MAX/2 using namespace std; inline int rd(){ int x=0,y=1;char c=getchar(); while(!isdigit(c)){if(c=='-')y=-y;c=getchar();} while(isdigit(c))x=x*10+c-'0',c=getchar(); return x*y; } struct node{ int x,y,num; node(int a,int b,int c){x=a,y=b,num=c;} node(){} }; int n,m; int a[N][N],dis[N][N][3]; queue<node>q; int tox[4]={-1,0,1,0}; int toy[4]={0,1,0,-1}; int main(){ n=rd(),m=rd(); for(int i=1; i<=n; i++){ for(int j=1; j<=n; j++){ a[i][j]=rd(); for(int k=0; k<3; k++)dis[i][j][k]=inf; } } dis[1][1][0]=0; q.push(node(1,1,0)); while(!q.empty()){ node now=q.front(); q.pop(); for(int i=0; i<4; i++){ int x=now.x+tox[i]; int y=now.y+toy[i]; if(x<1 || y<1 || x>n || y>n)continue; int len=m+(now.num==2)*a[x][y]; int num=(now.num+1)%3; if(dis[x][y][num]<=dis[now.x][now.y][now.num]+len)continue; dis[x][y][num]=dis[now.x][now.y][now.num]+len; q.push(node(x,y,num)); } } printf("%d\n",min(dis[n][n][0],min(dis[n][n][1],dis[n][n][2]))); return 0; } |
