hdu 1142 A Walk Through the Forest(최 단 경로+dfs)

http://acm.hdu.edu.cn/showproblem.php?pid=1142
대체적으로 제목:만약 에 a,b 사이 에 가장자리 가 있 으 면 ab 변 을 가 는 조건 은 b 가 목적지 까지 가 는 가장 짧 은 경로 가 a 가 목적지 까지 가 는 가장 짧 은 경로 보다 작다.이 요구 에 따라 가면 마지막 으로 1 에서 2 까지 의 경로 수 를 물 어보 세 요.
사고방식:먼저 2 까지 의 최 단 경 로 를 미리 처리한다.그리고 1dfs 에서 경로 수 를 찾 습 니 다.DAG 의 동적 계획 처럼 경로 수 를 구 합 니 다.

#include <stdio.h>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <string.h>
#define LL long long
#define _LL __int64

using namespace std;
const int INF = 0x3f3f3f3f;

int n,m;
int mapp[1100][1100];
int dis[1100];
int vis[1100];
int cnt[1100];

void init()
{
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= n; j++)
		{
			if(i != j)
				mapp[i][j] = INF;
			else mapp[i][j] = 0;
		}
	}
}

void dijstra(int s)
{
	memset(vis,0,sizeof(vis));
	memset(dis,INF,sizeof(dis));

	vis[s] = 1;

	for(int i = 1; i <= n; i++)
		dis[i] = mapp[s][i];

	for(int i = 1; i < n; i++)
	{
		int min = INF;
		int pos;

		for(int j = 1; j <= n; j++)
		{
			if(!vis[j] && min > dis[j])
			{
				min = dis[j];
				pos = j;
			}
		}

		vis[pos] = 1;

		for(int j = 1; j <= n; j++)
		{
			if(!vis[j] && dis[j] > dis[pos] + mapp[pos][j])
				dis[j] = dis[pos] + mapp[pos][j];
		}
	}
}

// 1 2     
int dfs(int s)
{
	if(s == 2)
		return cnt[2] = 1;

	if(cnt[s] >= 0)
		return cnt[s];
	else
	{
		int res = 0;
		for(int i = 1; i <= n; i++)
		{
			if(mapp[s][i] != INF && dis[i] < dis[s])
				res += dfs(i);
		}
		return cnt[s] = res;
	}
}

int main()
{
	int u,v,w;
	while(~scanf("%d",&n) && n)
	{
		scanf("%d",&m);
		init();

		while(m--)
		{
			scanf("%d %d %d",&u,&v,&w);
				mapp[u][v] = mapp[v][u] = w;
		}

		dijstra(2); //       
		
		memset(cnt,-1,sizeof(cnt));
		int ans = dfs(1);
		printf("%d
",ans);
	}
	return 0;
}