最短路+记忆化搜索
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[1010][1010]; int vexnum,arcnum; int vexs[1010]; } AMGraph; AMGraph G; int D[1010],path[1010],S[1010],dp[1010];///这里忽略掉path吧，没用到 const int maxint = 1000000000; int n,m; void createG(AMGraph &G) { int x,y,distance; for(int i = 1 ; i <=n; i++) for(int j =1; j<=n; j++) G.arcs[i][j] = maxint; ///建图，不连通的用一个能够满足题意的无穷大值表示 for(int i = 0; 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 = 1; v<=n; v++) { S[v] = 0; D[v] = G.arcs[v0][v]; if(D[v]<maxint) path[v] = v0; else path[v] = -1; } S[v0] = 1; D[v0] = 0; for(int i =2 ; i<=n; i++) { int minn = maxint; for( w = 1; w<=n; w++) if(!S[w]&&D[w]<minn) { v = w; minn = D[w]; } S[v] = 1; for(w = 1; 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==2)///到终点，找到一条路径 { return 1; } if(dp[v]) return dp[v];///计算过，直接返回 for(int i = 1; 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,2); memset(dp,0,sizeof(dp)); int ans = 0; ans = dfs(1); printf("%d ",ans); } return 0; }