【记忆化搜索+最短路】HDU 2833 WuKong

基德KID.1412

http://acm.hdu.edu.cn/showproblem.php?pid=2833

题意：求2条最短路径的最多公共点数
首先要说的是：求出最短路后，如果dist + map[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[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 = map;    dist = 0;    mark = 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] > -1)//记忆        return dp[a];    int i, j, v = 0;    //v是重要的临时值    if (a == b)//a==b可以一起往前走一步    {        v++;        for (i = 1; i <= n; i++)//枚举第一条最短路的可以到达a的前一个点        {            if (d1 + map[a] != d1[a])//ia不是最短路上的边                continue;            for (j = 1; j <= n; j++)//枚举第二条最短路的可以到达b的前一个点                if (d2[j] + map[j] == d2)                    v = max (v, dfs (i, j)+1);        }    }    for (i = 1; i <= n; i++)//a往前走一步        if (d1 + map[a] == d1[a])            v = max (v, dfs (i, b));    for (i = 1; i <= n; i++)//b往前走一步        if (d2 + map == d2)            v = max (v, dfs (a, i));    dp[a] = 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[v])                map[v] = map[v] = 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;}