Rt，代码如下:

// Problem : #114. car的旅行路线
// Contest : UOJ
// URL : http://【数据删除】/problem/114
// Memory Limit : 1024 MB
// Time Limit : 1000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
struct point
{
    long double x, y;
    point( long double x, long double y )
    {
        this->x = x;
        this->y = y;
    }
    point() {}
};
point add( point a, point b )
{
    return point( a.x + b.x, a.y + b.y );
}
int times( point a, point b )
{
    return ( a.x * b.x + a.y * b.y );
}
point get_point( point a, point v )
{
    return point( a.x + v.x, a.y + v.y );
}
point get_vector( point a, point b )
{
    return point( b.x - a.x, b.y - a.y );
}
bool checkrt( point a, point b )
{
    return ( times( a, b ) == 0 );
}
struct HeapNode
{
    long double d;
    int u;
    bool operator<( const HeapNode& rhs ) const
    {
        return d > rhs.d;
    }
};
struct Edge
{
    int from, to;
    long double dist;
    Edge( int from, int to, long double dist )
    {
        this->from = from;
        this->to = to;
        this->dist = dist;
    }
};
long double dis( point a, point b )
{
    return sqrt( ( a.x - b.x ) * ( a.x - b.x )
                 + ( a.y - b.y ) * ( a.y - b.y ) );
}
struct Graph
{
    int n, m;
    vector< Edge > edges;
    vector< int > G[ 100010 ];
    bool done[ 100010 ];
    long double d[ 100010 ];
    void init( int n )
    {
        this->n = n;
        for ( int i = 1; i <= n; i++ )
            G[ i ].clear();
        edges.clear();
    }
    void Addedge( int u, int v, long double w )
    {
        edges.push_back( ( Edge ){ u, v, w } );
        m = edges.size();
        G[ u ].push_back( m - 1 );
        G[ v ].push_back( m - 1 );
    }
    void dijkstra( int s )
    {
        priority_queue< HeapNode > Q;
        for ( int i = 1; i <= n; i++ )
            d[ i ] = 0x3f3f3f3f;
        d[ s ] = 0;
        memset( done, 0, sizeof( done ) );
        Q.push( ( HeapNode ){ 0, s } );
        while ( !Q.empty() )
        {
            HeapNode x = Q.top();
            Q.pop();
            int u = x.u;
            if ( done[ u ] )
                continue;
            done[ u ] = true;
            for ( auto i : G[ u ] )
            {
                Edge& e = edges[ i ];
                if ( d[ e.to ] > d[ u ] + e.dist )
                {
                    // cerr << d[ u ] << " " << e.dist << " " << endl;
                    d[ e.to ] = d[ u ] + e.dist;
                    Q.push( ( HeapNode ){ d[ e.to ], e.to } );
                }
            }
        }
    }
} g;
struct rectangle
{
    point a, b, c, d;
    point array[ 4 ];
    rectangle( point a, point b, point c )
    {
        point ab = get_vector( a, b );
        point ba = get_vector( b, a );
        point ac = get_vector( a, c );
        point ca = get_vector( c, a );
        point cb = get_vector( c, b );
        point bc = get_vector( b, c );
        if ( checkrt( ab, ac ) )
        {
            // cerr << "A" << endl;
            this->a = a;
            this->b = b;
            this->c = c;
            this->d = get_point( a, add( ab, ac ) );
        }
        else if ( checkrt( ba, bc ) )
        {
            // cerr << "B" << endl;
            this->a = a;
            this->d = c;
            this->b = b;
            this->c = get_point( b, add( ba, bc ) );
        }
        else
        {
            // cerr << "C" << endl;
            this->a = a;
            this->c = c;
            // cerr << ac.x << " " << ac.y << " " << bc.x << " " << bc.y << endl;
            this->b = get_point( c, add( ca, cb ) );
            this->d = b;
        }
        this->array[ 0 ] = this->a;
        this->array[ 1 ] = this->b;
        this->array[ 2 ] = this->c;
        this->array[ 3 ] = this->d;
    }
    rectangle() {}
} a[ 110 ];
int main()
{
    int T;
    cin >> T;
    while ( T-- )
    {
        int n, c, s, t;
        cin >> n >> c >> s >> t;
        g.init( 4 * n + 8 );
        for ( int i = 1; i <= n; i++ )
        {
            point a1, a2, a3;
            double ti;
            cin >> a1.x >> a1.y >> a2.x >> a2.y >> a3.x >> a3.y >> ti;
            a[ i ] = rectangle( a1, a2, a3 );
            for ( int j = 0; j < 4; j++ )
            {
                for ( int k = j + 1; k < 4; k++ )
                {
                    g.Addedge( 4 * i + j, 4 * i + k,
                               dis( a[ i ].array[ j ], a[ i ].array[ k ] )
                                   * ti );
                }
            }
        }
        for ( int i = 1; i <= n; i++ )
        {
            for ( int j = i + 1; j <= n; j++ )
            {
                for ( int k1 = 0; k1 < 4; k1++ )
                {
                    for ( int k2 = 0; k2 < 4; k2++ )
                    {
                        g.Addedge( 4 * i + k1, 4 * j + k2,
                                   dis( a[ i ].array[ k1 ], a[ j ].array[ k2 ] )
                                       * c );
                        /*cerr
                            << 4 * i + k1 << " " << 4 * j + k2 << " "
                            << dis( a[ i ].array[ k1 ], a[ j ].array[ k2 ] ) * c
                            << endl;*/
                    }
                }
            }
        }
        long double ans = 2000000000;
        for ( int i = 0; i < 4; i++ )
        {
            g.dijkstra( 4 * s + i );
            for ( int j = 0; j < 4; j++ )
            {
                // if ( g.d[ 4 * t + j ] != 0 )
                ans = min( ans, g.d[ 4 * t + j ] );
                // cerr << g.d[ 4 * t + j ] << endl;
            }
        }
        printf( "%.1Lf\n", ans );
    }
}