HDOJ 1428 漫步校园 （spfa+记忆搜索）

题目链接：(—_—) zZ

题目大意：我去， 题目看了半天才看懂， 是求当前这点A到终点的路径距离与下一点B到终点的路径是减小的路径有多少个。

比如A到终点的路径为10， B到终点的路径为5， 并可以通过A到B（为直接连通）那么这就是符合条件的一条路。

思路：用spfa求出每个点到终点的距离， 在dfs记忆搜索符合条件的， 注意范围（我又这样wa了，）

code：

#include <stdio.h>#include <string.h>#define inf 0x7fffffffstruct{    int v, pow, next;}edge[52*52*4];int n = 0, map[52][52], head[52*52], dis[52*52], dir[4][2] = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};__int64 choise[52][52];void init()//建图{    int i = 0, j = 0, k = 0, x = 0, y = 0, count = 0;    memset(head, -1, sizeof(head));    for(i = 1; i<=n; i++)    {        for(j = 1; j<=n; j++)        {            for(k = 0; k<4; k++)            {                x = i+dir[k][0], y = j+dir[k][1];                if(x>0 && x<=n && y>0 && y<=n)                {                    edge[count].pow = map[i][j]+map[x][y];                    edge[count].v = (x-1)*n+y;                    edge[count].next = head[(i-1)*n+j];                    head[(i-1)*n+j] = count++;                }            }        }    }}void spfa(){    int i = 0, p = 0, q = 0, row = 0, col = 0, front = 0, rear = 0, used[52*52], que[10000];    for(i = 1; i<=n*n; i++)    {        used[i] = 0;        dis[i] = inf;    }    dis[n*n] = map[n][n];    used[n*n] = 1;    que[rear++] = n*n;    while(front != rear)    {        p = que[front];        row = p%n == 0? p/n:p/n+1;//求在原图中的位置        col = p%n == 0?  n:p%n;        front = (front+1)%10000;        used[p] = 0;        for(q = head[p]; q != -1; q = edge[q].next)        {            if(dis[edge[q].v]>dis[p]+edge[q].pow-map[row][col])//多出的要减去            {                dis[edge[q].v] = dis[p]+edge[q].pow-map[row][col];                if(used[edge[q].v] == 0)                {                    used[edge[q].v] = 1;                    que[rear] = edge[q].v;                    rear = (rear+1)%10000;                }            }        }    }}__int64 dfs(int x, int y)//记忆搜索{    int i = 0, fx = 0, fy = 0;    if(choise[x][y]>0) return choise[x][y];    if(x == n && y == n) return 1;    for(i = 0; i<4; i++)    {        fx = x+dir[i][0]; fy = y+dir[i][1];        if(fx>0 && fx<=n && fy>0 && fy<=n)        {            if(dis[(fx-1)*n+fy]<dis[(x-1)*n+y])            {                choise[x][y] += dfs(fx, fy);            }        }    }    return choise[x][y];}int main(){    int i = 0, j = 0;    while(scanf("%d",&n) != EOF)    {        for(i = 1; i<=n; i++)            for(j = 1; j<=n; j++)                scanf("%d",&map[i][j]);        memset(choise, 0, sizeof(choise));        init();        spfa();        choise[1][1] = dfs(1, 1);        printf("%I64d\n",choise[1][1]);    }    return 0;}