2014年9月15日 星期一

2014/9/15 codevs 1041 Car的旅行路线

/*
    Floyd–Warshall
*/
// http://codevs.cn/problem/1041/
#include <iostream>
#include <cstdio>
#include <cmath>

using namespace std;

int N;
int s, t, A, B;

int INF = 1000000000;
int X[500], Y[500];

double dis(int a, int b)
{
    double dx = X[a]-X[b];
    double dy = Y[a]-Y[b];

    return sqrt(dx*dx+dy*dy);
}

double cost[500][500];

int main()
{
    scanf("%d", &N);

    for(int Ni = 0; Ni < N; Ni++)
    {
        scanf("%d %d %d %d", &s, &t, &A, &B); A--; B--;
        fill(cost[0], cost[499]+500, INF);

        for(int si = 0; si < s; si++)
        {
            for(int i = 0; i < 3; i++)
                scanf("%d %d", &X[si*4+i], &Y[si*4+i]);

            for(int i = 0; i < 3; i++)
            {
                swap(X[si*4], X[si*4+i]);
                swap(Y[si*4], Y[si*4+i]);

                int t1 = (X[si*4]-X[si*4+1])*(X[si*4]-X[si*4+2]);
                int t2 = (Y[si*4]-Y[si*4+1])*(Y[si*4]-Y[si*4+2]);

                if( t1+t2 == 0 ) break;
            }

            int k; scanf("%d", &k);

            X[si*4+3] = X[si*4+2]+X[si*4+1]-X[si*4];
            Y[si*4+3] = Y[si*4+2]+Y[si*4+1]-Y[si*4];

            for(int i = 0; i < 4; i++)
                for(int j = 0; j < 4; j++)
                    cost[si*4+i][si*4+j] = dis(si*4+i, si*4+j)*k;
        }

        for(int si = 0; si < s; si++)
            for(int sj = 0; sj < s; sj++)
            {
                if( si == sj ) continue;

                for(int i = 0; i < 4; i++)
                    for(int j = 0; j < 4; j++)
                        cost[si*4+i][sj*4+j] = dis(si*4+i, sj*4+j)*t;
            }

        for(int sk = 0; sk < s*4; sk++)
            for(int si = 0; si < s*4; si++)
                for(int sj = 0; sj < s*4; sj++)
                    cost[si][sj] = min(cost[si][sj], cost[si][sk]+cost[sk][sj]);

        double Ans = INF;

        for(int i = 0; i < 4; i++)
            for(int j = 0; j < 4; j++)
                Ans = min(Ans, cost[A*4+i][B*4+j]);

        printf("%.1lf", Ans); puts("");

    }
}

沒有留言:

張貼留言