Cod sursa(job #638451)

Utilizator irene_mFMI Irina Iancu irene_m Data 20 noiembrie 2011 21:25:03
Problema Portal3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.14 kb
#include <cstdio>
#include <iostream>

using namespace std;

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;
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, min;
    for( i = 1; i <= 7; ++i ){
        dist[ i ] = cost[ 0 ][ i ];
        use[ i ] = 0;
    }
    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 );

    cin >> T;

    for( ; T; T-- ){
        cin >> N >> M;
        cin >> P[ 1 ].x >> P[ 1 ].y >> P[ 2 ].x >> P[ 2 ].y >> C[ 1 ];
        cin >> P[ 3 ].x >> P[ 3 ].y >> P[ 4 ].x >> P[ 4 ].y >> C[ 2 ];
        cin >> P[ 5 ].x >> P[ 5 ].y >> P[ 6 ].x >> P[ 6 ].y >> C[ 3 ];
        initial_dist();
        dijkstra();
        cout << dist[ 7 ] << "\n";
    }
}