xfstart07
Get busy living or get busy dying

#include < iostream >
using   namespace  std;

int  N,M;
int  g[ 101 ][ 101 ];
int  m[ 101 ];
int  a[ 101 ];
int  b[ 101 ];
int  main()
{
    scanf(
" %d%d " , & N, & M);
    
int  k;
    
for ( int  i = 1 ;i <= N; ++ i)
        
for ( int  j = 1 ;j <= N; ++ j)
            
if (i == j) g[i][j] = 0 ;
            
else  g[i][j] = 0xFFFFFFF ;
    
for ( int  i = 1 ;i <= M; ++ i){
        scanf(
" %d " , & k);
        
for ( int  j = 1 ;j <= k; ++ j)
            scanf(
" %d " , & b[j]);
        
for ( int  t = 1 ;t < k; ++ t)
            
for ( int  j = t + 1 ;j <= k; ++ j)  if (t != j)
                g[b[t]][b[j]]
= g[b[j]][b[t]] = 4 ;
    }
    scanf(
" %d " , & M);
    
for ( int  i = 1 ;i <= M; ++ i)
        scanf(
" %d%d%d " , & m[i], & a[i], & b[i]);
    
for (k = 1 ;k <= N; ++ k)
        
for ( int  i = 1 ;i <= N; ++ i)  if (i != k)
            
for ( int  j = 1 ;j <= N; ++ j)  if (i != j && j != k)
                
if (g[i][j] > g[i][k] + g[k][j])
                    g[i][j]
= g[j][i] = g[i][k] + g[k][j];
    
int  loc,ans = 0x7FFFFFFF ;
    
for (k = 1 ;k <= N; ++ k){
        
int  sum = 0 bool  bo = 1 ;
        
for ( int  i = 1 ;i <= M; ++ i)
            
if (g[a[i]][k] == 0xFFFFFFF || ( ! b[i] && g[a[i]][k] > m[i])){
                bo
= 0 break ;
            }
            
else   if ( ! b[i]) sum += g[a[i]][k];
        
if (bo)
            
if (ans > sum){
                ans
= sum;
                loc
= k;
            }
    }
    
if (ans != 0x7FFFFFFF )
        printf(
" %d %d\n " ,loc,ans);
    
else  printf( " 0\n " );
    
return   0 ;
}




posted on 2009-05-31 22:57 xfstart07 阅读(120) 评论(0)  编辑 收藏 引用 所属分类: 代码库

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