HDU - 1142 A Walk Through the Forest

思路：再用最短路处理完后，就是求满足条件的个数，这里用到了记忆化搜索减少搜索

用dp[i]来表示i开始的满足条件的个数

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 1010;
const int INF = 1000000;

int num,road,map[MAXN][MAXN],dis[MAXN],dp[MAXN];
int vis[MAXN];

void dijkstra(int start){
	int t,k;
	memset(vis,0,sizeof(vis));
	for (int i = 1; i <= num; i++)
		dis[i] = map[start][i];
	dis[start] = 0;
	vis[start] = 1;
	for (int i = 1; i <= num; i++){
		t = INF;
		for (int j = 1; j <= num; j++)
			if (!vis[j] && t > dis[j])
				t = dis[k=j];
		if (t == INF)
			break;
		vis[k] = 1;
		for (int j = 1; j <= num; j++)
			if (!vis[j] && dis[j] > dis[k]+map[k][j])
				dis[j] = dis[k] + map[k][j];
	}
}

int dfs(int v){
	int sum = 0;
	if (dp[v] != -1)
		return dp[v];
	if (v == 2)
		return 1;
	for (int i = 1; i <= num; i++)
		if (map[v][i] != INF && dis[v] > dis[i])
			sum += dfs(i);
	dp[v] = sum;
	return dp[v];
}

int main(){
	int x,y,cost;
	while (scanf("%d",&num) != EOF && num){
		scanf("%d",&road);
		for (int i = 1; i <= num; i++){
			dp[i] = -1;
			for (int j = 1; j <= num; j++)
				map[i][j] = INF;
		}
		for (int i = 1; i <= road; i++){
			scanf("%d%d%d",&x,&y,&cost);
			map[x][y] = map[y][x] = cost;
		}
		dijkstra(2);
		printf("%d\n",dfs(1));
	}
	return 0;
}

HDU - 1142 A Walk Through the Forest,布布扣,bubuko.com

HDU - 1142 A Walk Through the Forest

原文：http://blog.csdn.net/u011345136/article/details/22897745