hdu_1428 漫步校园

             由“他考虑从A区域到B区域仅当存在一条从B到机房的路线比任何一条从A到机房的路线更近(否则可能永远都到不了机房了…)” 知道，先要求出每个点到终点的最短路径。

  接着DFS得到可以满足条件的路径个数（记忆化搜索）。

我的代码：

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
using namespace std;
#define MAXN 55
#define INF 0xffffff
int map[MAXN][MAXN];
int dis[MAXN][MAXN];
int n;
int xx[]={0,0,-1,1};
int yy[]={1,-1,0,0};
struct Node
{int x,y;
};
void SPFA(int sx,int sy)  //求最短路径。
{Node S;S.x=sx;S.y=sy;queue<Node> Q;bool vis[MAXN][MAXN]={0};Q.push(S);dis[sx][sy]=map[sx][sy];vis[sx][sy]=1;while(!Q.empty()){Node u=Q.front();Q.pop();vis[u.x][u.y]=0;for(int i=0;i<4;i++){int nx=u.x+xx[i];int ny=u.y+yy[i];if(nx>=1&&nx<=n&&ny>=1&&ny<=n&&dis[nx][ny]>dis[u.x][u.y]+map[nx][ny]){dis[nx][ny]=dis[u.x][u.y]+map[nx][ny];if(vis[nx][ny]==0){vis[nx][ny]=1;Node p;p.x=nx;p.y=ny;Q.push(p);}}}}
}
__int64 ans[MAXN][MAXN];__int64 DFS(int sx,int sy)  //记忆化搜索得到路径数。
{if(sx==n && sy==n)  return 1;if(ans[sx][sy]) return ans[sx][sy];for(int i=0;i<4;i++){int nx=sx+xx[i];int ny=sy+yy[i];if(nx>=1&&nx<=n && ny>=1&&ny<=n && dis[nx][ny]<dis[sx][sy]){ans[sx][sy]+= DFS(nx,ny);}}return ans[sx][sy];}int main()
{while(~scanf("%d",&n)){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++) scanf("%d",&map[i][j]);}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++) dis[i][j]=INF;}SPFA(n,n);  //SPAF求最短路劲。memset(ans,0,sizeof(ans));DFS(1,1);printf("%I64d\n",ans[1][1]);}return 0;
}