这一星期我在学习单源最短路径，今天是这一星期的最后一天。我半写半参考的写出了这一题，要用到DFS+Dijsktra。
题目是让求一个点到另一个点的“前进的”(就是越走离家越近，这是一个难点，不然就做不出来)路径的条数。算法思想是：先求出家到每一个顶点的最短路径，然后用深搜求出从公司到家的路径的条数。
#include <stdio.h>
#include <memory.h>
#define debug 1
#define N 1010
//要注意不要把Max定义的太大，不然会在做加法时溢出，
// 当然，要是不做加法，就没事了，可以定义为2147483647
//也可以用 __int64 ，但是那样的效率比较低
#define Max 10000000
int n ;
int map[N][N], dis[N], used[N], num[N] ;
void Input( )
{
int i, j, x, m, y, distance ;
for( i=1; i<=n; ++i ){
for( j=1; j<=n; ++j ){
map[i][j] = Max ;
}
//自己到自己的最短路径是0
map[i][i] = 0 ;
}
scanf("%d", &m ) ;
for( i=0; i<m; ++i ){
scanf("%d%d%d", &x, &y, &distance ) ;
//用无向图来存储数据
map[x][y] = distance ;
map[y][x] = distance ;
}
}
void Dijstra( int v )
{
int i, j, min, index ;
for( i=1; i<=n; ++i ){
//求家到各个顶点的初始路径的距离，如果没有路径，就是Max
dis[i] = map[v][i] ;
//用来标记是否已经求过
used[i] = 0 ;
}
// 从家里出发，家已经走过，标记为1，下同
used[v] = 1 ;
for( i=1; i<=n; ++i ){
min = Max ;
index = v ;
//找到与每一个已标记过的顶点之间距离最小的顶点
for( j=1; j<=n; ++j ){
if( !used[j] && min > dis[j] ){
index = j ;
min = dis[j] ;
}
}
//已经找到，标记
used[index] = 1 ;
//更新与刚找到的顶点相邻的顶点的最短路径
for( j=1; j<=n; ++j ){
if( dis[j] > dis[index] + map[index][j] )
dis[j] = dis[index] + map[index][j] ;
}
}
}
int DFS( int nod )
{
int i, count ;
//如果已到家，就返回1，表示找到了一条路
if( nod == 2 )
return 1 ;
//如果这一点已经求过，就返回这一点到家的路径的条数
if( num[nod] > 0 )
return num[nod] ;
count = 0 ;
//对每一个顶点进行判断，并求路径的条数
for( i=1; i<=n; ++i ){
if( map[i][nod]<Max && dis[i]<dis[nod] )
count += DFS( i ) ;
}
//标记路径的条数，并返回值
num[nod] = count ;
return count ;
}
int main()
{
// 输入输出的重定向，便于调试，在提交时要把debug改成0
#if debug
freopen("C:\\Documents and Settings\\Administrator\\桌面\\in.in","r",stdin) ;
freopen("C:\\Documents and Settings\\Administrator\\桌面\\out.out","w",stdout) ;
#endif
while( scanf("%d",&n) && n ){
//读入数据
Input( ) ;
//调用Dijsktra 求家到每一个节点的最短路径
Dijstra( 2 ) ;
// 数据初始化
memset( num, 0, sizeof(num) ) ;
// 用深搜求的路径的条数
printf("%d\n", DFS( 1 ) ) ;
}
return 0 ;
}