這一星期我在學(xué)習(xí)單源最短路徑，今天是這一星期的最后一天。我半寫(xiě)半?yún)⒖嫉膶?xiě)出了這一題，要用到DFS+Dijsktra。
題目是讓求一個(gè)點(diǎn)到另一個(gè)點(diǎn)的“前進(jìn)的”(就是越走離家越近，這是一個(gè)難點(diǎn)，不然就做不出來(lái))路徑的條數(shù)。算法思想是：先求出家到每一個(gè)頂點(diǎn)的最短路徑，然后用深搜求出從公司到家的路徑的條數(shù)。
#include <stdio.h>
#include <memory.h>
#define debug 1
#define N 1010
//要注意不要把Max定義的太大，不然會(huì)在做加法時(shí)溢出，
// 當(dāng)然，要是不做加法，就沒(méi)事了，可以定義為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 ) ;
//用無(wú)向圖來(lái)存儲(chǔ)數(shù)據(jù)
map[x][y] = distance ;
map[y][x] = distance ;
}
}
void Dijstra( int v )
{
int i, j, min, index ;
for( i=1; i<=n; ++i ){
//求家到各個(gè)頂點(diǎn)的初始路徑的距離，如果沒(méi)有路徑，就是Max
dis[i] = map[v][i] ;
//用來(lái)標(biāo)記是否已經(jīng)求過(guò)
used[i] = 0 ;
}
// 從家里出發(fā)，家已經(jīng)走過(guò)，標(biāo)記為1，下同
used[v] = 1 ;
for( i=1; i<=n; ++i ){
min = Max ;
index = v ;
//找到與每一個(gè)已標(biāo)記過(guò)的頂點(diǎn)之間距離最小的頂點(diǎn)
for( j=1; j<=n; ++j ){
if( !used[j] && min > dis[j] ){
index = j ;
min = dis[j] ;
}
}
//已經(jīng)找到，標(biāo)記
used[index] = 1 ;
//更新與剛找到的頂點(diǎn)相鄰的頂點(diǎn)的最短路徑
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 ;
//如果這一點(diǎn)已經(jīng)求過(guò)，就返回這一點(diǎn)到家的路徑的條數(shù)
if( num[nod] > 0 )
return num[nod] ;
count = 0 ;
//對(duì)每一個(gè)頂點(diǎn)進(jìn)行判斷，并求路徑的條數(shù)
for( i=1; i<=n; ++i ){
if( map[i][nod]<Max && dis[i]<dis[nod] )
count += DFS( i ) ;
}
//標(biāo)記路徑的條數(shù)，并返回值
num[nod] = count ;
return count ;
}
int main()
{
// 輸入輸出的重定向，便于調(diào)試，在提交時(shí)要把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 ){
//讀入數(shù)據(jù)
Input( ) ;
//調(diào)用Dijsktra 求家到每一個(gè)節(jié)點(diǎn)的最短路徑
Dijstra( 2 ) ;
// 數(shù)據(jù)初始化
memset( num, 0, sizeof(num) ) ;
// 用深搜求的路徑的條數(shù)
printf("%d\n", DFS( 1 ) ) ;
}
return 0 ;
}