漫步校园
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
题解：设F[i][j]表示，从（i，j），跑到终点的方案数，我们用spfa预处理出当前节点到终点的距离，对于距离变大的，就不可以进行状态转移，
然后记忆化搜索，把可行的地方的方案数加起来就可以了。
#include<iostream> #include<stdio.h> #include<queue> #include<algorithm> #include<stdlib.h> #include<cstring> #define ll long long using namespace std; int n; ll mp[100][100],dis[100][100]; int addx[5]={0,1,-1,0,0},addy[5]={0,0,0,1,-1}; int have[100][100]; ll f[100][100]; void spfa(int starx,int stary){ queue<int> xx,yy; while(!xx.empty()) xx.pop(); while(!yy.empty()) yy.pop(); xx.push(starx); yy.push(stary); dis[starx][stary]=mp[starx][stary],have[starx][stary]=1; while(!xx.empty()){ int nowx=xx.front(); int nowy=yy.front(); xx.pop(),yy.pop(); have[nowx][nowy]=0; for(int i=1;i<=4;i++){ int tox=nowx+addx[i],toy=nowy+addy[i]; if(tox<=0||tox>n||toy>n||toy<=0) continue; if(dis[tox][toy]>dis[nowx][nowy]+mp[tox][toy]) { dis[tox][toy]=dis[nowx][nowy]+mp[tox][toy]; //printf("nowx=%d nowy=%d tox=%d toy=%d ",nowx,nowy,tox,toy); //printf("dis[nowx][nowy]=%d dis[tox][toy]=%d mp[tox][toy]=%d ",dis[nowx][nowy],dis[tox][toy],mp[tox][toy]); if(have[tox][toy]==0){ xx.push(tox); yy.push(toy); have[tox][toy]=1; } } } } } void cl(){ memset(mp,0,sizeof(mp)); memset(f,0,sizeof(f)); memset(have,0,sizeof(have)); memset(dis,127,sizeof(dis)); } ll dp(int x,int y){ if(f[x][y]) return f[x][y]; if(x==n&&y==n) return 1; ll now=0; for(int i=1;i<=4;i++){ int tox=x+addx[i]; int toy=y+addy[i]; if(tox<=0||tox>n||toy>n||toy<=0) continue; if(dis[tox][toy]<dis[x][y]) now+=dp(tox,toy); } return f[x][y]=now; } int main(){ while(scanf("%d",&n)!=EOF){ cl(); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>mp[i][j]; spfa(n,n); printf("%lld ",dp(1,1)); } }