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

zoj2504_Help John!

          这一题仍然是最短路径,一次AC!好高兴啊。题目是单纯的最短路径的小变形,只要从妈妈说的第二个路口开始找最短路径开始就可以了。

#include <stdio.h>
#define DEBUG 1

const int N=1111 ;
const int Max=0xfffffff ;
int n, sum, map[N][N], dis[N], used[N], mo[30002] ;

void Dijstra( )
{
    
int i, j, index, min ;
    
for( i=1; i<=n; ++i ){
        
//从第二个路口开始找最短路径,因为,第一个
        
//路口是必须走的,因为妈妈看着我呢! 
        dis[i] = map[mo[2]][i] ;
        used[i] 
= 0 ;
    }

    used[
1= 1 ;
    used[mo[
2]] = 1 ;
    
for( i=1; i<=n; ++i ){
        min 
= Max ;
        
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!used[j] && dis[j] > dis[index]+map[index][j] )
                dis[j] 
= dis[index]+map[index][j] ;
    }

    
//计算差值 
    printf("Y %d\n", sum-dis[n] ) ;
}


int main()
{
    
#if DEBUG
     freopen(
"C:\\Documents and Settings\\Administrator\\桌面\\in.txt","r",stdin);
     freopen(
"C:\\Documents and Settings\\Administrator\\桌面\\out.txt","w",stdout);
     
#endif
     
     
int i, j, k, r, di, flag, x, y, sets, mother ;
     scanf(
"%d"&sets ) ;
     
for( k=1; k<=sets; ++k ){
        printf(
"TEST %d ", k ) ;
        scanf(
"%d%d"&n, &r ) ;
        
for( i=1; i<=n; ++i ){
            
for( j=1; j<=n; ++j )
                map[i][j] 
= Max ;
            map[i][i] 
= 0 ;
        }
    
        
for( i=1; i<=r; ++i ){
            scanf(
"%d%d%d"&x, &y, &di ) ;
            map[x][y] 
= map[y][x] = di ;
        }

        scanf(
"%d"&mother ) ;
        
for( i=1; i<=mother; ++i )
            scanf(
"%d"&mo[i] ) ;
        sum 
= flag = 0 ;
        
//妈妈说第一条路必须走,因为她说她在看着我
        
//但是最后还是要减掉的,所以要走,但是不加上。
        for( i=2; i<mother; ++i ){
            
//如果没路,就输出 N !妈妈和我开玩笑呢!
            
// 继续下一次读入信息 
            if( map[mo[i]][mo[i+1]] == Max ){
                printf(
"N\n") ;
                flag 
= 1 ;
                
break ;
            }

            
//按照妈妈说的路线走,看看要走多远 
            sum += map[mo[i]][mo[i+1]] ;
        }

        
if!flag )
            Dijstra( ) ;    
    }

    
return 0 ;
}

posted on 2009-05-07 21:13 祝你好运! 阅读(117) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理