我队列开小了，改成循环队列就过了，真坑爹.... 先SPFA求出各点到终点的最短距离，然后在记忆化搜一遍，记录路径数目，注意在搜的过程中，如果移动点的dis大于等于当前位置，那么
我队列开小了，改成循环队列就过了，真坑爹....
先SPFA求出各点到终点的最短距离，然后在记忆化搜一遍，记录路径数目，注意在搜的过程中，如果移动点的dis大于等于当前位置，那么就是不可以走的，反之就是可以走的。
#include <stdio.h>
#include <cstring>
#define inf 1e9
using namespace std;
int n,t[52][52],dis[52][52];
__int64 path[52][52];
bool visit[52][52];
int h[4]={1,-1,0,0};
int g[4]={0,0,1,-1};
void SPFA(){
int i,j,k,front=0,rear=0;
int x[3000],y[3000];
memset(visit,0,sizeof(visit));
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
dis[i][j]=inf;
dis[n][n]=t[n][n];
x[0]=n;y[0]=n;
rear++;
visit[n][n]=1;
while(front!=rear){
visit[x[front]][y[front]]=0;
for(i=0;i<4;i++){
int xx=x[front]+h[i];
int yy=y[front]+g[i];
if(xx<1 || xx>n || yy<1 || yy>n)
continue;
if(dis[xx][yy]>dis[x[front]][y[front]]+t[xx][yy]){
dis[xx][yy]=dis[x[front]][y[front]]+t[xx][yy];
if(!visit[xx][yy]){
visit[xx][yy]=1;
x[rear]=xx,y[rear]=yy;rear++;
rear=rear%3000;
}
}
}
front++;
front=front%3000;
}
}
__int64 dfs(int x,int y){
if(x==n && y==n)
return 1;
if(path[x][y]>=0)
return path[x][y];
__int64 sum=0;
for(int i=0;i<4;i++){
int xx=x+h[i];
int yy=y+g[i];
if(xx<1 || xx>n || yy<1 || yy>n)
continue;
if(dis[xx][yy]>=dis[x][y])
continue;
sum+=dfs(xx,yy);
}
path[x][y]=sum;
return sum;
}
int main(){
while(scanf("%d",&n)!=EOF){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)
scanf("%d",&t[i][j]);
}
SPFA();
memset(path,-1,sizeof(path));
printf("%I64d\n",dfs(1,1));
}
}