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 阅读(80) 评论(0)  编辑 收藏 引用 所属分类: 代码库

 只有注册用户登录后才能发表评论。 【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库 相关文章: