随笔 - 19, 文章 - 0, 评论 - 2, 引用 - 0
数据加载中……

杭电1142 A Walk Through the Forest

        这一星期我在学习单源最短路径,今天是这一星期的最后一天。我半写半参考的写出了这一题,要用到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, 0sizeof(num) ) ;
        
// 用深搜求的路径的条数 
        printf("%d\n", DFS( 1 ) ) ; 
    }
        
    
return 0 ;
}

posted on 2009-05-03 17:35 祝你好运! 阅读(337) 评论(1)  编辑 收藏 引用

评论

# re: 杭电1142 A Walk Through the Forest  回复  更多评论   

我想请问下,你的程序测试如下数据:
5 7
1 3 2
1 4 2
3 4 3
1 5 12
4 2 34
5 2 24
5 3 11
输出4,为什么不是2?
如果有空的话请联系我:357384984@qq.com
2011-04-23 21:47 | Veegin

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理