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[57][57]; int dis[57][57]; __int64 dp[57][57]; int vis[57][57]; int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}}; bool operator < (node a,node b) { return a.d>b.d; } void dfs() { priority_queue<node> que; memset(vis,0,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] = 1; dis[tmp.x][tmp.y] = tmp.d; for(int i = 0;i < 4;i++) { next.x = tmp.x+dir[i][0]; next.y = tmp.y+dir[i][1]; if(next.x<1||next.x>n||next.y<1||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] != -1) return dp[x][y]; else { node next; dp[x][y] = 0; for(int i = 0;i < 4;i++) { next.x = x+dir[i][0]; next.y = y+dir[i][1]; if(next.x<1||next.x>n||next.y<1||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,-1,sizeof(dp)); for(int i = 1;i <= n;i++) for(int j = 1;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] = 1; cout<<solve(1,1)<<endl; } return 0; }