2019-05-21 P1027 Car的旅行路线

题目链接：https://www.luogu.org/problemnew/show/P1027

Dijstra找一下最短路径，这里把每一个机场当成一个定点，然后多次使用dijstra找最短路径，取最小值作为结果

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

int n;
const int maxn=4*100+10;
const double INF = 10000000000;
double d[maxn],G[maxn][maxn],x[maxn],y[maxn],used[maxn],EPS=1e-8;
double dis(double x1,double y1,double x2,double y2){
    double dx=x1-x2,dy=y1-y2;
    return sqrt(dx*dx+dy*dy);
}

void fourp(int x1,int y1,int x2,int y2,int x3,int y3,int &x4,int &y4){
    if( abs((x2-x1)*(x3-x1)+(y2-y1)*(y3-y1))<EPS ){
        x4=x2+x3-x1;
        y4=y2+y3-y1;
        return ;
    }
    if( abs((x1-x2)*(x3-x2)+(y1-y2)*(y3-y2))<EPS ){
        x4=x1+x3-x2;
        y4=y1+y3-y2; 
        return ;
    }
    if( abs((x1-x3)*(x2-x3)+(y1-y3)*(y2-y3))<EPS ){
        x4=x1+x2-x3;
        y4=y1+y2-y3;
        return ;
    }
}
double Dijstra(int s,int t){
    for(int i=0;i<n;i++) d[i]=INF;
    //cout<<"test"<<endl;
    //for(int i=0;i<n;i++) cout<<d[i]<<"\t";
    memset(used,0,sizeof(used));
    d[s]=0;
    for(int i=0;i<n;i++){
        int u=-1,Min=INF;
        for(int j=0;j<n;j++){
            if(!used[j] && Min>d[j]){//找到一个距离最短点 
                Min=d[j];
                u=j;
            }
        }
        //标记访问
        used[u]=true;
        for(int v=0;v<n;v++){
            if(!used[v] && G[u][v]!=INF && G[u][v]+d[u]<d[v]){
                d[v]=G[u][v]+d[u];
            }
        }  
    }
    //dis[t*4-4]-dis[t*4-1]
    //cout<<"test"<<endl;
    //for(int i=0;i<n;i++) cout<<d[i]<<"\t";
    return min(min(d[t*4-4],d[t*4-3]),min(d[t*4-2],d[t*4-1]));
}
int main(void){
    //freopen("in.txt","r",stdin);
    int s,t,A,B;
    int T,x1,x2,x3,y1,y2,y3,x4,y4,ts;
    scanf("%d",&T);
    while(T--){
        //cout<<"T:"<<T<<endl;
        scanf("%d%d%d%d",&s,&t,&A,&B);
        
        n=s*4;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++) G[i][j]=INF;
        }
        
        for(int i=0;i<s;i++){
            scanf("%d%d%d%d%d%d%d",&x1,&y1,&x2,&y2,&x3,&y3,&ts);
            fourp(x1,y1,x2,y2,x3,y3,x4,y4);
            x[i*4]=x1,y[i*4]=y1;
            x[i*4+1]=x2,y[i*4+1]=y2;
            x[i*4+2]=x3,y[i*4+2]=y3;
            x[i*4+3]=x4,y[i*4+3]=y4;
            vector<int>a;
            for(int k=0;k<4;k++) a.push_back(i*4+k);
            for(int k=0;k<4;k++){
                for(int m=0;m<4;m++){
                    G[a[k]][a[m]]=dis(x[a[k]],y[a[k]],x[a[m]],y[a[m]])*ts;
                }
            }
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(G[i][j]==INF) G[i][j]=dis(x[i],y[i],x[j],y[j])*t;
                //防止之前使用一个城市之间的道路进行 
                //cout<<G[i][j]<<"\t\t";
            }
            //cout<<endl;
        }
        
        double mindis=INF;
        for(int i=0;i<4;i++) mindis=min(mindis,Dijstra(A*4-4+i,B));
        printf("%.1lf\n",mindis);
    }
    return 0;
}