最短路+记忆化搜索
HDU 1142 A Walk Through the Forest
链接：http://acm.hdu.edu.cn/showproblem.php?pid=1142
> 题意：找出不同的路径条数，假如jimmy要从A走到B的话满足jimmy从B到家的距离比从A到家的距离短
> 这样我们可以通过最短路算法，找出从家（看成源点）到各个点的最短路径长度，记做D[v]。 然后就可以从起点(office)
> dfs，首先从某点i到某点j走得通，然后满足D[j]<D[j],则可以往下搜索，直到终点(house)，普通的dfs是会超时的，N都是1000了，不加剪枝啥的，dfs生成树那么大，肯定会TLE的。
> 所以这里要用记忆话搜索，减少重复计算某个一个状态的值。 对于最短路和记忆化，本人也是刚刚学习的，最短路模仿的数据结构书上的
> dijkstra，记忆化也是借鉴别人的思路。不过我想说说子结构的重复计算 比如 0
> 1 2
> 3 4 5 6
> 7 8 9
> 10 dfs(0) 是 从0到10的所以路径条数（假设走法随意，只要深度+1即可) dfs(4）是从4到10的路径条数，1可以到4,2也可以到4.
> 那么dfs(1)后肯定已经计算过dfs(4)了，dfs(2)就没必要再计算，直接用这个结果就行了 所以可以用个数组保存即可
> 再啰嗦一句，题库分这题在并查集里面，有哪位大神能教我并查集怎么做？
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
typedef struct
{
int arcs[][];
int vexnum,arcnum;
int vexs[];
} AMGraph;
AMGraph G;
int D[],path[],S[],dp[];///这里忽略掉path吧，没用到
const int maxint = ;
int n,m;
void createG(AMGraph &G)
{
int x,y,distance;
for(int i = ; i <=n; i++)
for(int j =; j<=n; j++)
G.arcs[i][j] = maxint; ///建图，不连通的用一个能够满足题意的无穷大值表示
for(int i = ; i<m; i++)
{
scanf("%d%d%d",&x,&y,&distance);
G.arcs[x][y] = G.arcs[y][x] = distance;
}
}
void shortestflyod(AMGraph &G,int v0)///书上代码，不懂得还是看书吧
{
int v,w;
for( v = ; v<=n; v++)
{
S[v] = ;
D[v] = G.arcs[v0][v];
if(D[v]<maxint) path[v] = v0;
else path[v] = -;
}
S[v0] = ;
D[v0] = ;
for(int i = ; i<=n; i++)
{
int minn = maxint;
for( w = ; w<=n; w++)
if(!S[w]&&D[w]<minn)
{
v = w;
minn = D[w];
}
S[v] = ;
for(w = ; w<=n; w++)
if(!S[w]&&D[v]+G.arcs[v][w]<D[w])
{
D[w] = D[v] + G.arcs[v][w];
path[w] = v;
}
}
}
int dfs(int v)
{
if(v==)///到终点，找到一条路径
{
return ;
}
if(dp[v]) return dp[v];///计算过，直接返回
for(int i = ; i<=n; i++)
if(G.arcs[v][i]!=maxint&&D[i]<D[v])//连通且满足条件
dp[v] += dfs(i);//dp[v] 等于下面一个分支的路径数之和
return dp[v];
}
int main()
{
while(scanf("%d",&n)&&n)
{
scanf("%d",&m);
createG(G);
shortestflyod(G,);
memset(dp,,sizeof(dp));
int ans = ;
ans = dfs();
printf("%d\n",ans);
}
return ;
}