Pagini recente » Cod sursa (job #632510) | Cod sursa (job #905447) | Cod sursa (job #445505) | Borderou de evaluare (job #1330250) | Cod sursa (job #635463)
Cod sursa(job #635463)
#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";
}
}