【记忆化搜寻+最短路】HDU 2833 WuKong
【记忆化搜索+最短路】HDU 2833 WuKong
http://acm.hdu.edu.cn/showproblem.php?pid=2833
题意:求2条最短路径的最多公共点数
首先要说的是:求出最短路后,如果dist[u] + map[u][v] = dist[v],则uv这条边必定在最短路上
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 305 int 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; }