zcmimi's blog

查看原题

点击跳转

建图比较麻烦的最短路问题

将每个城市考虑为4个机场

每个机场两两之间互相连边,若同一个城市,走高速,否则走航线

需要注意的是找出根据三个机场找出第四个机场时的分类讨论

#include<bits/stdc++.h>
const int N=111;
typedef double db;
struct pt{int x,y;}a[N*4];
void rd(pt&a){scanf("%d%d",&a.x,&a.y);}
int DIS(pt a,pt b){return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);}
db dis(pt a,pt b){return sqrt(DIS(a,b));}
pt get(pt a,pt b,pt c){
    if(DIS(a,b)+DIS(a,c)==DIS(b,c))
        return (pt){c.x-(a.x-b.x),c.y-(a.y-b.y)};
    else if(DIS(a,b)+DIS(b,c)==DIS(a,c))
        return (pt){c.x+(a.x-b.x),c.y+(a.y-b.y)};
    else 
        return (pt){b.x+(a.x-c.x),b.y+(a.y-c.y)};
}
int j,T[N],bl[N*4];
struct node{
    int x;db d;
    bool operator<(const node&b)const{return d>b.d;}
};
std::priority_queue<node>q;
db d[N*4];bool v[N*4];
void solve(){
    int n,t,A,B;j=0;
    scanf("%d%d%d%d",&n,&t,&A,&B);
    for(int i=1,j=1;i<=n;++i,j+=4)
        rd(a[j]),rd(a[j+1]),rd(a[j+2]),a[j+3]=get(a[j],a[j+1],a[j+2]),
        bl[j]=bl[j+1]=bl[j+2]=bl[j+3]=i,
        scanf("%d",T+i);
    memset(d,126,sizeof d);memset(v,0,sizeof v);
    for(int i=A*4-3;i<=A*4;++i)q.push((node){i,d[i]=0});
    while(!q.empty()){
        int x=q.top().x;q.pop();
        if(v[x])continue;else v[x]=1;
        for(int i=1;i<=n*4;++i)if(i!=x){
            db nd=d[x]+1.0*dis(a[x],a[i])*(bl[x]==bl[i]?T[bl[x]]:t);
            if(nd<d[i])q.push((node){i,d[i]=nd});
        }
    }
    db ans=d[B*4];
    for(int i=B*4-3;i<B*4;++i)if(d[i]<ans)ans=d[i];
    printf("%.1f\n",ans);
}
int main(){
    int T;scanf("%d",&T);
    while(T--)solve();
}
LG 1027 Car的旅行路线
comment评论
Search
search