hdu1142（dj+记忆化搜索）

题意：给你n各点，m行关于这些点的联通关系，以及距离，求从1这个点到2这个点之间，下一个点到2这个点比当前点到2这个点的距离要小的路径的条数......

思路：dj+记忆化搜索.......

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
typedef __int64 ss;
#define max 1010
#define p 10000000
ss a[max][max];
ss n,m;
ss dp[max],dist[max];
void dj(ss n,ss v,ss v1)
{
	ss i,j,k,min;
	ss s[max];
	for(i=1;i<=n;i++)
	{
		dist[i]=a[v][i];
		s[i]=0;
	}
	s[v]=1;
	for(i=2;i<=n;i++)
	{
		min=p;
		k=1;
		for(j=1;j<=n;j++)
			if(s[j]==0&&dist[j]<min)
			{
				k=j;
				min=dist[j];
			}
		s[k]=1;
		for(j=1;j<=n;j++)
			if(s[j]==0)
			if(a[k][j]<p&&dist[k]+a[k][j]<dist[j])
				dist[j]=dist[k]+a[k][j];
	}
}
ss dfs(ss num)
{
	if(dp[num])   return dp[num];
	if(num==2)   return 1;
	ss sum=0;
	for(ss i=1;i<=n;i++)
	{
		if(i==num)
		continue;
		if(a[num][i]!=p&&dist[num]>dist[i])
		{
			sum+=dfs(i);
		}
	}
	dp[num]=sum;
	return dp[num];
}
int main()
{
	while(scanf("%I64d",&n)>0&&n)
	{
		scanf("%I64d",&m);
		for(ss i=0;i<=n;i++)
		for(ss j=0;j<=n;j++)
		a[i][j]=p;
		for(ss i=0;i<=n;i++)
		a[i][i]=0;
		for(ss i=1;i<=m;i++)
		{
			ss tmp,x,y;
			scanf("%I64d%I64d%I64d",&x,&y,&tmp);
			if(a[x][y]>tmp)
			{
				a[x][y]=a[y][x]=tmp;
			}
		}
		dj(n,2,1);
		//for(int i=1;i<=n;i++)
		//printf("%I64d
",dist[i]);
		memset(dp,0,sizeof(dp));
		printf("%I64d
",dfs(1));
	}
	return 0;
}