5 6 1 3 2 1 4 2 3 4 3 1 5 12 4 2 34 5 2 24 7 8 1 3 1 1 4 1 3 7 1 7 4 1 7 5 1 6 7 1 5 2 1 6 2 1 0
2 4
题意：一片森林里有一个人，从家去工作要穿越整个森林，他现在想从工作的地方回家。森林里有n个地点，m条路，工作地点编号为1，家编号为2.他想经过这样的地点k：从地点k到家的距离比任意从工作地点到家的距离都短，问这样的地点有多少个？
解析：先用Dijkstra处理反向一下，记录从他家到各个地点的最短路径，然后再用记忆化搜索，计算家到工作地点的路径总条数。
AC代码：
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
#define INF 1e7 + 2
const int maxn = 1000 + 5;
int n, m;
int w[maxn][maxn], d[maxn], v[maxn];
int ans[maxn]; //answer
void dijkstra(int s){
memset(v, 0, sizeof(v));
for(int i=1; i<=n; i++) d[i] = i==s ? 0 : INF;
for(int i=1; i<=n; i++){
int x, m = INF;
for(int y=1; y<=n; y++)
if(!v[y] && d[y] <= m) m = d[x = y];
v[x] = 1;
for(int y=1; y<=n; y++) d[y] = min(d[y], d[x] + w[x][y]);
}
}
int dfs(int k, int n){
if(ans[k]) return ans[k]; //记忆化，否则超时！！！
if(k == 2) return 1;
for(int i=1; i<=n; i++){
if(w[k][i] < INF && d[k] > d[i]) //满足条件
ans[k] += dfs(i, n);
}
return ans[k];
}
int main(){
#ifdef sxk
freopen("in.txt", "r", stdin);
#endif //sxk
int x, y, z;
while(scanf("%d%d", &n, &m)!=EOF && n){
memset(ans, 0, sizeof(ans));
for(int i=1; i<=n; i++)
for(int j=1; j<=i; j++)
w[i][j] = w[j][i] = i==j ? 0 : INF;
for(int i=0; i<m; i++){
scanf("%d%d%d", &x, &y, &z);
w[x][y] = w[y][x] = min(w[x][y], z);
}
dijkstra(2); //家作为源点
printf("%d\n", dfs(1, n));
}
return 0;
}
hdu 1142 A Walk Through the Forest （Dijkstra + 记忆化搜索）
原文：http://blog.csdn.net/u013446688/article/details/42966087