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
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int const INF = 0x3fffffff;
int const MAX = 1005;
int dis[MAX], dp[MAX];
int map[MAX][MAX];
bool vis[MAX];
int n, m;
void Dijkstra(int v0)
{
memset(vis, false, sizeof(vis));
for(int i = 1; i <= n; i++)
dis[i] = INF;
for(int i = 1; i <= n; i++)
dis[i] = map[v0][i];
vis[v0] = true;
dis[v0] = 0;
for(int i = 1; i < n; i++)
{
int u = 0, mi = INF;
for(int j = 1; j <= n; j++)
{
if(!vis[j] && dis[j] < mi)
{
mi = dis[j];
u = j;
}
}
vis[u] = true;
for(int k = 1; k <= n; k++)
if(!vis[k])
dis[k] = min(dis[k], dis[u] + map[u][k]);
}
}
int DFS(int x)
{
if(dp[x])
return dp[x];
if(x == 2)
return 1;
int tmp = 0;
for(int i = 1; i <= n; i++)
if(dis[x] > dis[i] && map[x][i] != INF)
tmp += DFS(i);
return dp[x] = tmp;
}
int main()
{
while(scanf("%d", &n) != EOF && n)
{
scanf("%d", &m);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
map[i][j] = INF;
for(int i = 0; i < m; i++)
{
int u, v, w;
scanf("%d %d %d", &u, &v, &w);
map[u][v] = map[v][u] = w;
}
Dijkstra(2);
memset(dp, 0, sizeof(dp));
printf("%d\n", DFS(1));
}
}HDU 1142 A Walk Through the Forest (Dijkstra + 记忆化搜索 好题)
原文：http://blog.csdn.net/tc_to_top/article/details/45276461