HDU3665

最短路

floyd

#include<stdio.h>
#include<string.h>
const int maxn =11;
int sea[ maxn ];
int mat[ maxn ][ maxn ];
const int inf=999999;

void init(){
    memset( sea,0,sizeof(sea));
    for( int i=0;i<maxn;i++ )
        for( int j=0;j<maxn;j++ )
            mat[ i ][ j ]=inf;
}

int main(){
    int n;
    while( scanf("%d",&n)!=EOF ){
        init();
        for( int i=0;i<n;i++ ){
            int a,b;
            scanf("%d%d",&a,&b);
            sea[ i ]=b;
            while( a-- ){
                int pos,dis;
                scanf("%d%d",&pos,&dis);
                mat[ i ][ pos ]=dis;
            }
        }

        for( int k=0;k<n;k++ ){
            for( int i=0;i<n;i++ ){
                for( int j=0;j<=n;j++ ){
                    if( mat[ i ][ k ]!=inf && mat[ k ][ j ]!=inf && mat[i][j]>(mat[i][k]+mat[k][j]) ){
                        mat[i][j]=(mat[i][k]+mat[k][j]);
                    }
                }
            }
        }

        int ans1=inf;
        for( int i=1;i<n;i++ ){
            if( ans1>mat[0][i] && sea[i]!=0 && mat[0][i]!=inf ){
                ans1=mat[0][i];
            }
        }

        printf("%d\n",ans1);
    }
    return 0;
}