這一星期我在學習單源最短路徑，今天是這一星期的最后一天。我半寫半參考的寫出了這一題，要用到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 ;
}