【最短絡+dfs+dijkstra】杭電hdu 1142 A Walk Through the Forest

/* THE PROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//
	Copyright (c) 2011 panyanyany All rights reserved.

	URL   : http://acm.hdu.edu.cn/showproblem.php?pid=1142
	Name  : 1142 A Walk Through the Forest

	Date  : Friday, January 13, 2012
	Time Stage : 4 hours

	Result: 
5252336	2012-01-13 16:18:59	Accepted	1142
78MS	4124K	2027 B
C++	pyy

5252323	2012-01-13 16:16:15	Wrong Answer	1142
62MS	4124K	2046 B
C++	pyy


Test Data :

Review :
        ，             ……         
       ，        ，      ……
             ……
             ：
http://www.cnblogs.com/liuqidong/archive/2010/07/28/1787217.html
http://www.cppblog.com/Dreams/archive/2010/09/04/78871.html


     ，               
     ：
5 6
1 3 3
1 4 2
3 4 1
1 5 12
4 2 34
5 2 24
      2

          = =！
         ～～   
//----------------------------------------------------------------------------*/

#include <stdio.h>
#include <string.h>

#define min(x, y)	((x) < (y) ? (x) : (y))
#define max(x, y)	((x) > (y) ? (x) : (y))

#define INF		0x3f3f3f3f
#define MAXN	1002

bool	used[MAXN] ;

int		n, m ;
int		map[MAXN][MAXN], dist[MAXN], pathCnt[MAXN] ;

//   dijkstra       home    
void dijkstra ()
{
	int i, j ;
	int iMinPath, MinPath ;

	memset (used, 0, sizeof (used)) ;

	for (i = 1 ; i <= n ; ++i)
		dist[i] = map[2][i] ;
	dist[2] = 0 ;

	for (i = 1 ; i <= n ; ++i)
	{
		iMinPath = 0 ;
		MinPath = INF ;

		for (j = 1 ; j <= n ; ++j)
			if (!used[j] && dist[j] < MinPath)
			{
				iMinPath = j ;
				MinPath = dist[j] ;
			}

		used[iMinPath] = true ;

		for (j = 1 ; j <= n ; ++j)
		{
			if (!used[j])
				dist[j] = min (dist[iMinPath] + map[iMinPath][j], dist[j]) ;
		}
	}
}

//   dfs             
int dfs (const int start)
{
	if (start == 2)
		return 1 ;
	//   start       ，     
	if (pathCnt[start] != -1)
		return pathCnt[start] ;

	int i, sum ;

	sum = 0 ;

	for (i = 1 ; i <= n ; ++i)
	{
		// start   i          ，
		//        i   home        start   home    
		/*
		dist[start] > dist[i]              ，          
		 ：
		5 6
		1 3 3
		1 4 2
		3 4 1
		1 5 12
		4 2 34
		5 2 24
		      2 （         ）
		         ：
		(map[start][i] == dist[start] - dist[i]))
		        ……
		*/
		if ((map[start][i] != INF) && dist[start] > dist[i])
		{
			sum += dfs (i) ;
		}
	}

	return pathCnt[start] = sum ;
}

int main ()
{
	int i ;
	int x, y, c ;
	while (scanf ("%d", &n), n)
	{
		scanf ("%d", &m) ;
		memset (map, INF, sizeof (map)) ;

		for (i = 0 ; i < m ; ++i)
		{
			scanf ("%d%d%d", &x, &y, &c) ;
			map[x][y] = map[y][x] = c ;
		}

		dijkstra () ;
		memset (pathCnt, -1, sizeof (pathCnt)) ;

		printf ("%d
", dfs(1)) ;
	}
	return 0 ;
}