csu 1106 最优对称路径 最短路+记忆化搜索.

题目链接:

csu1106

解题思路:

首先思考如何得到一条对称的路径:

分别从起点和终点出发,并走对称的方向,最后在对角线汇合,所有点权之和即是这条路径的的路程

我们很容易发现,模拟 终点到对角线的过程 是多余的,因为它的路径和 起点到对角线所走的路径 是对称的…..

我们只需要将整个地图沿对角线对折,重合的点累加,那么我们从起点(已和终点重合)出发,走到对角线的任意一处都是一条对称路径

接着考虑最短路的方案数:

我们首先通过最短路算法, 求出走到图中每个点需要的最短距离

考虑到每个点u的路径数可以从它的四个方向的点v得到

只要满足 dis[u]+value[v]==dis[v]

那么path[u]+=path[v]

这个过程可以用记忆化搜索完成..

最后得到所有方案数

代码:

#include<iostream>#include<cstdio>#include<cstring>#include<queue>#define mod 1000000009#define maxn 205#define INF 0x3f3f3f3fusing namespace std;struct node{int x,y,s;} head,t;long long dp[maxn][maxn];int dir[4][2]= {1,0,0,1,-1,0,0,-1};int dis[maxn][maxn];int vis[maxn][maxn];int v[maxn][maxn];int n,min_dis;int ok(int x,int y){if(x<1||y<1||x+y>n+1)return 0;return 1;}void spfa(){memset(dis,INF,sizeof(dis));memset(vis,0,sizeof(vis));int tx,ty;min_dis=INF;queue<node>q;q.push((node){1,1});dis[1][1]=v[1][1];while(!q.empty()){head=q.front();q.pop();vis[head.x][head.y]=0;if(head.x+head.y==n+1){if(dis[head.x][head.y]<min_dis)min_dis=dis[head.x][head.y];continue;}for(int i=0; i<4; i++){tx=head.x+dir[i][0];ty=head.y+dir[i][1];if(ok(tx,ty)&&dis[tx][ty]>dis[head.x][head.y]+v[tx][ty]){dis[tx][ty]=dis[head.x][head.y]+v[tx][ty];if(!vis[tx][ty]){vis[tx][ty]=1;q.push((node){tx,ty});}}}}}long long dfs(int x,int y) //记忆化搜索{if(dp[x][y]!=-1)return dp[x][y];if(x+y==n+1)return dp[x][y]=dis[x][y]==min_dis;dp[x][y]=0;int tx,ty;for(int i=0;i<4;i++){tx=x+dir[i][0];ty=y+dir[i][1];if(ok(tx,ty)&&(dis[x][y]+v[tx][ty]==dis[tx][ty])) //满足最短的dp[x][y]=(dp[x][y]+dfs(tx,ty))%mod;}return dp[x][y];}int main(){while(~scanf("%d",&n)&&n){for(int i=1; i<=n; i++)for(int j=1; j<=n; j++){scanf("%d",&v[i][j]);if(i+j>n+1)v[n+1-j][n+1-i]+=v[i][j];//对折}spfa();memset(dp,-1,sizeof(dp));printf("%lld\n",dfs(1,1));}return 0;}

版权声明:本文为博主原创文章,,未经博主允许不得转载。

有理想在的地方,地狱就是天堂

csu 1106 最优对称路径 最短路+记忆化搜索.

相关文章:

你感兴趣的文章:

标签云: