Cod sursa(job #635452)

Utilizator irene_mFMI Irina Iancu irene_m Data 19 noiembrie 2011 11:45:21
Problema Portal3 Scor 0
Compilator cpp Status done
Runda .com 2011 Marime 2.19 kb
#include <cstdio>

const int MAX_N = 10;
const long long INF = 5000000000;

struct point{
    long long x, y;
}   P[ MAX_N ];

long long cost[ MAX_N ][ MAX_N ], dist[ MAX_N ], C[ MAX_N ], use[ MAX_N ], gen[ MAX_N ], N, M, min;
int T;

long long abs( long long X){
    if( X >= 0 )
        return X;
    return - X;
}

long long minim( long long A, long long B ){
    if( A < B )
        return A;
    return B;
}

void initial_dist(){

    int i, j;
    for( i = 1; i < 6; ++i )
        for( j = i + 1; j <= 6; ++j )
            cost[ i ][ j ] = cost[ j ][ i ] = abs( P[ i ].x - P[ j ].x ) + abs( P[ i ].y - P[ j ].y );

    cost[ 1 ][ 2 ] = cost[ 2 ][ 1 ] = minim( cost[ 1 ][ 2 ], C[ 1 ] );
    cost[ 3 ][ 4 ] = cost[ 4 ][ 3 ] = minim( cost[ 3 ][ 4 ], C[ 2 ] );
    cost[ 5 ][ 6 ] = cost[ 6 ][ 5 ] = minim( cost[ 5 ][ 6 ], C[ 3 ] );

    for( i = 1; i <= 6; ++i ){
        cost[ 0 ][ i ] = P[ i ].x + P[ i ].y;
        cost[ i ][ 7 ] = N - P[ i ].x + M - P[ i ].y;
    }

    cost[ 0 ][ 7 ] = N + M;

}

long long minim2(){
    long long minc = INF;
    int i, poz;
    for( i = 1; i <= 7; ++i )
        if( ! use[ i ] && dist[ i ] < minc )
            minc  = dist[i], poz = i;
    return poz;
}

void dijkstra(){

    int i, j;
    for( i = 1; i <= 7; ++i )
        dist[ i ] = cost[ 0 ][ i ];
    use[ 0 ] = 1;

    for( i = 1; i <= 7; ++i )
    {
        min = minim2();
        use [ min ] = 1;
        for( j = 1; j <= 7; ++j )
            if( dist[ j ] > dist[ min ] + cost[ min ][ j ] )
                dist[ j ] = dist[ min ] + cost[ min ][ j ];
    }

}


int main(){
    freopen( "portal3.in", "r", stdin );
    freopen( "portal3.out", "w", stdout );

    scanf( "%d", &T );

    for( ; T; T-- ){
        scanf( "%lld %lld", &N, &M );
        scanf( "%lld %lld %lld %lld %lld", &P[ 1 ].x, &P[ 1 ].y, &P[ 2 ].x, &P[ 2 ].y, &C[ 1 ] );
        scanf( "%lld %lld %lld %lld %lld", &P[ 3 ].x, &P[ 3 ].y, &P[ 4 ].x, &P[ 4 ].y, &C[ 2 ] );
        scanf( "%lld %lld %lld %lld %lld", &P[ 5 ].x, &P[ 5 ].y, &P[ 6 ].x, &P[ 6 ].y, &C[ 3 ] );
        initial_dist();
        min = INF;
        dijkstra();
        printf( "%lld\n", dist[ 7 ] );
    }
}