【记忆化搜索+最短路】HDU 2833 WuKong
http://acm.hdu.edu.cn/showproblem.php?pid=2833题意：求2条最短路径的最多公共点数
首先要说的是：求出最短路后，如果dist + map = dist，则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, d1, d2, dp;bool mark;void init (){ for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) map = 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 = map; dist = 0; mark = true; while (1) { mins = inf; for (j = 1; j <= n; j++) if (!mark && dist < mins) mins = dist, v = j; if (mins == inf) break; mark = true; for (j = 1; j <= n; j++) if (!mark && dist + map < dist) dist = dist + map; }}int dfs (int a, int b){ if (dp > -1)//记忆 return dp; int i, j, v = 0; //v是重要的临时值 if (a == b)//a==b可以一起往前走一步 { v++; for (i = 1; i <= n; i++)//枚举第一条最短路的可以到达a的前一个点 { if (d1 + map != d1)//ia不是最短路上的边 continue; for (j = 1; j <= n; j++)//枚举第二条最短路的可以到达b的前一个点 if (d2 + map == d2) v = max (v, dfs (i, j)+1); } } for (i = 1; i <= n; i++)//a往前走一步 if (d1 + map == d1) v = max (v, dfs (i, b)); for (i = 1; i <= n; i++)//b往前走一步 if (d2 + map == d2) v = max (v, dfs (a, i)); dp = 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) map = map = w; } scanf ("%d%d%d%d", &A, &B, &C, &D); dp = 0; if (A == C)//dfs重要返回条件 dp = 1; dijk (A, d1); dijk (C, d2); printf ("%d\n", dfs (B, D));//dfs(A, C)会超时……要从终点走回起点 } return 0;}
页:
[1]