本文主要是介绍hdu 2833 WuKong(最短路径+记忆化搜索)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://acm.hdu.edu.cn/showproblem.php?pid=2833
大致题意：给定一个无向图，以及悟空和师傅起点与终点，求它们分别从起点到终点的最短路径中经过相同的点的最大个数。
思路：首先dijkstra求出最短路，那么如果有dis[a] + map[a][b] = dis[b]，则边（a,b）一定在最短路径上。根据这一定理可以求出所有最短路径。然后类似于求最长公共子序列求经过的相同点的最大个数。
即若a==b ,dp[a][b] = max(dp[i][j]+1)
否则 dp[a][b] = max(dp[a][j],dp[i][b])，其中i,j分别是a,b的直接前驱节点。
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <string.h>
#include <queue>
#include <string>
#define LL long long
#define _LL __int64
using namespace std;
const int INF = 1<<28;
const int maxn = 310;int Map[maxn][maxn];
int n,m;
int s1,t1,s2,t2;
int dis1[maxn],dis2[maxn];
int dp[maxn][maxn];void init()
{for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++)Map[i][j] = INF;}
}void dijkstra(int s, int f)
{int dis[maxn],vis[maxn];memset(vis,0,sizeof(vis));for(int i = 1; i <= n; i++)dis[i] = Map[s][i];vis[s] = 1;dis[s] = 0;for(int i = 1; i <= n; i++){int Min = INF,pos = -1;for(int j = 1; j <= n; j++){if(!vis[j] && dis[j] < Min){Min = dis[j];pos = j;}}if(pos == -1) break;vis[pos] = 1;for(int j = 1; j <= n; j++){if(!vis[j] && dis[j] > dis[pos] + Map[pos][j])dis[j] = dis[pos] + Map[pos][j];}}if(f == 1)memcpy(dis1,dis,sizeof(dis));else memcpy(dis2,dis,sizeof(dis));
}int dfs (int a, int b)
{if(a == s1 && b == s2)return dp[s1][s2];if(dp[a][b] > -1)return dp[a][b]; //记忆化int v = 0;if(a == b) // dp[a][b] = max(dp[i][j]+1){v++;for(int i = 1; i <= n; i++){if(dis1[i] + Map[i][a] != dis1[a]) continue;for(int j = 1; j <= n; j++)if(dis2[j] + Map[j][b] == dis2[b])v = max(v,dfs(i,j)+1);}return dp[a][b] = v;}//dp[a][b] = max(dp[i][b],dp[a][j]).v = 0;for(int i = 1; i <= n; i++){if(dis1[i] + Map[i][a] == dis1[a])v = max(v,dfs(i,b));}for(int i = 1; i <= n; i++){if(dis2[i] + Map[i][b] == dis2[b])v = max(v,dfs(a,i));}return dp[a][b] = v;
}int main()
{while(~scanf("%d %d",&n,&m)){init();if(n == 0 && m == 0) break;int u,v,w;for(int i = 1; i <= m; i++){scanf("%d %d %d",&u,&v,&w);if(w < Map[u][v])Map[u][v] = Map[v][u] = w;}scanf("%d %d %d %d",&s1,&t1,&s2,&t2);memset(dp,-1,sizeof(dp));dp[s1][s2] = 0;if(s1 == s2) // 注意起点相同的情况dp[s1][s2] = 1;dijkstra(s1,1);dijkstra(s2,2);int ans = dfs(t1,t2);printf("%d\n",ans);}return 0;
}
这篇关于hdu 2833 WuKong(最短路径+记忆化搜索)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
