hdu 1142 A Walk Through the Forest Dijkstra+记忆搜索

#include<iostream>

using namespace std;

const int MAX=2147483647;

int n,m;
int t1,t2,len;
int map[1005][1005];
int ans[1005];
int isvisit[1005];
int answer;

void Dijkstra();
int DFS(int k);

int main()
{
	while(cin>>n,n)
	{
		answer=0;
		memset(isvisit,-1,sizeof(isvisit));
		for(int i=1;i<=n;i++)
		{
			ans[i]=MAX;
			for(int j=1;j<=n;j++)
			{
				map[i][j]=MAX;
			}
		}

		cin>>m;

		for(i=0;i<m;i++)
		{
			cin>>t1>>t2>>len;
			
			if(map[t1][t2]>len)
				map[t1][t2]=map[t2][t1]=len;
		}

		Dijkstra();

//		for(i=1;i<=n;i++)
//		{
//			cout<<ans[i]<<endl;
//		}

		cout<<DFS(1)<<endl;
	}
	return 0;
}

void Dijkstra()
{
	int visit[1005]={0};
	int k;

	ans[2]=0;

	for(int i=1;i<=n;i++)
	{
		k=-1;

		for(int j=1;j<=n;j++)
		{
			if(!visit[j] && ( k==-1 || ans[j]<ans[k]) )
				k=j;
		}

		visit[k]=1;

		for(j=1;j<=n;j++)
		{
			if(!visit[j] && ans[j]>ans[k]+map[k][j] && map[k][j]!=MAX)
				ans[j]=ans[k]+map[k][j];
		}
	}
}

int DFS(int k)
{
	int temp=0;

	if(isvisit[k]!=-1)
		return isvisit[k];
	if(k==2)
	{
		return 1;
	}
	for(int i=1;i<=n;i++)
	{
		if(map[k][i]!=MAX && ans[k]>ans[i])
			temp+=DFS(i);
	}

	isvisit[k]=temp;
	return temp;
}