wikioi-天梯-提高一等-最短路-1041：Car的旅行路線

題目描述 Description

又到暑假了，住在城市A的Car想和朋友一起去城市B旅遊。她知道每個城市都有四個飛機場，分别位于一個矩形的四個頂點上，同一個城市中兩個機場之間有一條筆直的高速鐵路，第I個城市中高速鐵路了的機關裡程價格為Ti，任意兩個不同城市的機場之間均有航線，所有航線機關裡程的價格均為t。

那麼Car應如何安排到城市B的路線才能盡可能的節省花費呢?她發現這并不是一個簡單的問題，于是她來向你請教。

任務

找出一條從城市A到B的旅遊路線，出發和到達城市中的機場可以任意選取，要求總的花費最少。

輸入描述 Input Description

第一行為一個正整數n(0<=n<=10)，表示有n組測試資料。

每組的第一行有四個正整數s，t，A，B。

S(0<S<=100)表示城市的個數，t表示飛機機關裡程的價格，A，B分别為城市A，B的序号，(1<=A，B<=S)。

接下來有S行，其中第I行均有7個正整數xi1，yi1，xi2，yi2，xi3，yi3，Ti，這當中的(xi1，yi1)，(xi2，yi2)，(xi3，yi3)分别是第I個城市中任意三個機場的坐标，T I為第I個城市高速鐵路機關裡程的價格。

輸出描述 Output Description

共有n行，每行一個資料對應測試資料。

樣例輸入 Sample Input

1

3 10 1 3

1 1 1 3 3 1 30

2 5 7 4 5 2 1

8 6 8 8 11 6 3

樣例輸出 Sample Output

47.5

類型：圖論  難度：2

題意：給定s個機場，每個機場是個矩形，給出其中任意三個點的坐标，每個機場的四個點兩兩之間有公路，給出每個機場的6條公路的機關價格ti，機場之間的航線的機關價格為t，求從機場A到機場B的最小價格。

分析：

1、先求出每個矩形的第四個點的坐标，方法是先找到三個點中距離最大的兩個點，即為對角線，若12為對角線，34為對角線，那麼x1+x2=x3+x4，y1+y2=y3+y4，即可求出第四個點的坐标。

2、求出任意兩點的直接連接配接的價格，若為一個機場内的點，則為dis*ti，若為兩個機場的點，則為dis*t

3、周遊機場A的四個點，分别用dij方法計算其到機場B的四個點的最短路，取最小的，即為結果

注意：

1、dij方法計算單源最短路：設求點i到其他所有點最短路，那麼先找到和點i距離最近的點，如j，置定j，周遊j的鄰點k，若d[i][k]>d[i][j]+d[j][k]，證明經過點j，i和k的距離變小，更新d[i][k]。然後繼續下一循環，直到找到終點。

2、用一個标記數組f[i][j]記錄已經計算出的最短路的點，若f[i][j]=1，則i到j的最短路已經算出。防止重複計算。

代碼：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<iomanip>
using namespace std;

int s,t,a,b;
double pos[110][4][2],ti[110],w[110][4][110][4];
bool f[110][4][110][4];

void callastp(double m[][2])
{
    double d01,d02,d12,d;
    int a1,a2,b;
    d01 = pow(m[0][0]-m[1][0],2)+pow(m[0][1]-m[1][1],2);
    d02 = pow(m[0][0]-m[2][0],2)+pow(m[0][1]-m[2][1],2);
    d12 = pow(m[1][0]-m[2][0],2)+pow(m[1][1]-m[2][1],2);
    
    if(d01>=d02 && d01>=d12)
    {
        a1 = 0;
        a2 = 1;
        b = 2;
    }
    if(d02>=d01 && d02>=d12)
    {
        a1 = 0;
        a2 = 2;
        b = 1;
    }
    if(d12>=d02 && d12>=d01)
    {
        a1 = 1;
        a2 = 2;
        b = 0;
    }
    
    m[3][0] = m[a1][0]+m[a2][0]-m[b][0];
    m[3][1] = m[a1][1]+m[a2][1]-m[b][1];
}

double caldis(double x[], double y[])
{
    return sqrt(pow(x[0]-y[0],2)+pow(x[1]-y[1],2));
}

double dij(int m,int x,int n,int y)
{
    if(m==n)
        return 0;
    if(f[m][x][n][y])
        return w[m][x][n][y];
    
    bool ch[110][4];
    memset(ch,0,sizeof(ch));
    
    while(1)
    {
        int mini,minj,minn;
        mini = minj = minn = -1;
        for(int i=1; i<=s; i++)
        {
            for(int j=0; j<4; j++)
            {
                if(i==m && j==x)
                    continue;
                if(ch[i][j]) 
                    continue;
                if(minn<0 || w[m][x][i][j]<minn)
                {
                    minn = w[m][x][i][j];
                    mini = i;
                    minj = j;
                }
            }
        }
        f[m][x][mini][minj] = 1;
        ch[mini][minj] = 1;
        if(mini==n && minj==y)
        {
            //cout<<m<<" "<<x<<" "<<n<<" "<<y<<" "<<w[m][x][n][y]<<endl;
            return w[m][x][n][y];
        }
        for(int i=1; i<=s; i++)
        {
            for(int j=0; j<4; j++)
            {
                if(w[m][x][mini][minj]+w[mini][minj][i][j]<w[m][x][i][j])
                {
                    w[m][x][i][j] = w[m][x][mini][minj]+w[mini][minj][i][j];
                }
            }
        }
    }
}

int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        cin>>s>>t>>a>>b;
        for(int i=1; i<=s; i++)
        {
            for(int j=0; j<3; j++)
                cin>>pos[i][j][0]>>pos[i][j][1];
            cin>>ti[i];
            
            callastp(pos[i]);
            //cout<<pos[i][3][0]<<" "<<pos[i][3][1]<<endl;
        }
        memset(w,0,sizeof(w));
        for(int i=1; i<=s; i++)
        {
            for(int j=0; j<4; j++)
            {
                for(int k=j+1; k<4; k++)
                    w[i][j][i][k] = w[i][k][i][j] = caldis(pos[i][j],pos[i][k])*ti[i];
                for(int k=i+1; k<=s; k++)
                    for(int l=0; l<4; l++)
                        w[i][j][k][l] = w[k][l][i][j] = caldis(pos[i][j],pos[k][l])*t;
            }
        }
        memset(f,0,sizeof(f));
        double ans = -1;
        for(int i=0; i<4; i++)
        {
            for(int j=0; j<4; j++)
            {
                if(!f[a][i][b][j])
                    dij(a,i,b,j);
                if(ans<0 || w[a][i][b][j]<ans)
                    ans = w[a][i][b][j];
            }
        }
        cout<<fixed<<showpoint<<setprecision(1)<<ans<<endl;
    }
}