Problem Description
LL 最近沉迷于AC不能自拔，每天寝室、机房两点一线。由于长时间坐在电脑边，缺乏运动。他决定充分利用每次从寝室到机房的时间，在校园里散散步。整个HDU 校园呈方形布局，可划分为n*n个小方格，代表各个区域。例如LL居住的18号宿舍位于校园的西北角，即方格(1,1)代表的地方，而机房所在的第三实验 楼处于东南端的(n,n)。因有多条路线可以选择，LL希望每次的散步路线都不一样。另外，他考虑从A区域到B区域仅当存在一条从B到机房的路线比任何一 条从A到机房的路线更近(否则可能永远都到不了机房了…)。现在他想知道的是，所有满足要求的路线一共有多少条。你能告诉他吗?
Input
每组测试数据的第一行为n(2=<n<=50)，接下来的n行每行有n个数，代表经过每个区域所花的时间t(0<t<=50)(由于寝室与机房均在三楼，故起点与终点也得费时)。
Output
针对每组测试数据，输出总的路线数(小于2^63)。
Sample Input
3 1 2 3 1 2 3 1 2 3 3 1 1 1 1 1 1 1 1 1
Sample Output
1 6
思路：
这题再加上之前的那道老鼠题，算是记忆化搜索的模板题了，现在来学真是没觉得有什么难度，理顺了题目的思路，看了kuangbin大神的AC代码后，凭着思路在脑中复原代码修正后AC了
题目说A->B点的要求是B点到终点的多个距离中，肯定存在一个dis是小于A点所有到终点的距离的，而A点所有到终点的距离中就会包括通过B到达终点的距离————对这种逻辑进行一下总结，就会发现它让你求的就是起点到终点相同长度最短路的条数。
知道了这点之后，我们就可以开始计算所有的最短路了
计算最短路就是用Dijkstra，但是这个题这样做就麻烦了，其实这道题目用的方法Dijkstra是相同的，他们实质都是相同的，即每次对选入最短路线集合的点，松弛他的所有邻边。对于原始的Dij而言，我们用的for扫描整个数组，然后找出相邻的边，再对他们进行松弛操作。
都记录了最短距离之后，在递归求得第一个点的答案。
#include <iostream>
#include <cstring>
#include <queue>
using namespace std; struct node {
int x,y;
int d;
};
int n;
int map[][];
int dis[][];
__int64 dp[][];
int vis[][];
int dir[][] = {{,},{-,},{,},{,-}}; bool operator < (node a,node b) {
return a.d>b.d;
} void dfs()
{
priority_queue<node> que;
memset(vis,,sizeof(vis));
node tmp,next;
tmp.x = n;
tmp.y = n;
tmp.d = map[n][n];
que.push(tmp);
while(!que.empty())
{
tmp = que.top();
que.pop();
if(vis[tmp.x][tmp.y])
continue;
vis[tmp.x][tmp.y] = ;
dis[tmp.x][tmp.y] = tmp.d;
for(int i = ;i < ;i++) {
next.x = tmp.x+dir[i][];
next.y = tmp.y+dir[i][];
if(next.x<||next.x>n||next.y<||next.y>n||vis[next.x][next.y])
continue;
next.d = tmp.d + map[next.x][next.y];
que.push(next);
}
}
} __int64 solve(int x,int y)
{
if(dp[x][y] != -) return dp[x][y];
else {
node next;
dp[x][y] = ;
for(int i = ;i < ;i++) {
next.x = x+dir[i][];
next.y = y+dir[i][];
if(next.x<||next.x>n||next.y<||next.y>n)
continue;
next.d = dis[next.x][next.y];
if(next.d < dis[x][y])
dp[x][y]+=solve(next.x,next.y);
}
return dp[x][y];
}
} int main()
{
while(cin>>n)
{
memset(dp,-,sizeof(dp));
for(int i = ;i <= n;i++)
for(int j = ;j <= n;j++)
cin>>map[i][j];
dfs();
/*测试最小距离
cout<<endl<<"~~~"<<endl;
for(int i = 1;i <= n;i++)
for(int j = 1;j <= n;j++){
cout<<dis[i][j]<<' ';
if(j == n)
cout<<endl;
}
*/
dp[n][n] = ;
cout<<solve(,)<<endl;
}
return ;
}