【记忆化搜索+最短路】HDU 2833 WuKong
http://acm.hdu.edu.cn/showproblem.php?pid=2833
题意：求2条最短路径的最多公共点数
首先要说的是：求出最短路后，如果dist[u] + map[u][v] = dist[v]，则uv这条边必定在最短路上
#include <iostream>#include <fstream>#include <algorithm>#include <string>#include <set>//#include <map>#include <queue>#include <utility>#include <iomanip>#include <stack>#include <list>#include <vector>#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>//#include <ctime>#include <ctype.h>using namespace std;#define LL __int64#define inf 0x3fffffff#define M 305int n, map[M][M], d1[M], d2[M], dp[M][M];bool mark[M];void init (){ for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) map[i][j] = inf; memset (dp, -1, sizeof(dp));}void dijk (int u, int dist[]){ memset (mark, false, sizeof(mark)); int mins, i, j, v; for (i = 1; i <= n; i++) dist[i] = map[u][i]; dist[u] = 0; mark[u] = true; while (1) { mins = inf; for (j = 1; j <= n; j++) if (!mark[j] && dist[j] < mins) mins = dist[j], v = j; if (mins == inf) break; mark[v] = true; for (j = 1; j <= n; j++) if (!mark[j] && dist[v] + map[v][j] < dist[j]) dist[j] = dist[v] + map[v][j]; }}int dfs (int a, int b){ if (dp[a][b] > -1)//记忆 return dp[a][b]; int i, j, v = 0; //v是重要的临时值 if (a == b)//a==b可以一起往前走一步 { v++; for (i = 1; i <= n; i++)//枚举第一条最短路的可以到达a的前一个点 { if (d1[i] + map[i][a] != d1[a])//ia不是最短路上的边 continue; for (j = 1; j <= n; j++)//枚举第二条最短路的可以到达b的前一个点 if (d2[j] + map[j][b] == d2[b]) v = max (v, dfs (i, j)+1); } } for (i = 1; i <= n; i++)//a往前走一步 if (d1[i] + map[i][a] == d1[a]) v = max (v, dfs (i, b)); for (i = 1; i <= n; i++)//b往前走一步 if (d2[i] + map[i][b] == d2[b]) v = max (v, dfs (a, i)); dp[a][b] = v; return v;}int main(){ int m, u, v, w, A, B, C, D; while (scanf ("%d%d", &n, &m), (n||m)) { init (); while (m--) { scanf ("%d%d%d", &u, &v, &w); if (w < map[u][v]) map[u][v] = map[v][u] = w; } scanf ("%d%d%d%d", &A, &B, &C, &D); dp[A][C] = 0; if (A == C)//dfs重要返回条件 dp[A][C] = 1; dijk (A, d1); dijk (C, d2); printf ("%d\n", dfs (B, D));//dfs(A, C)会超时……要从终点走回起点 } return 0;}