2019 年百度之星·程序设计大赛 - 初赛一 C. Mindis 离散化+dijkstra

题意：中文题面

思路：

　　先将所有题目给出的点离散化一下，得到一张n*m的网格，n和m最大都是400，所以我们只需要枚举每个加强的区域，将属于这个区域的边处理一下（所有横着的和竖着的边，暴力处理即可），然后相邻的点建边，建图，跑最短路即可。

　　$mp[x][y][k]$表示网格上横坐标$x$纵坐标$y$，方向为k（0,1,2,3表示上右下左）这条离散化后长度为1的边被矩形覆盖的次数（初始值为1），时间就是离散化前的长度除以次数.然后建边跑dijkstra。

　　比赛最后几分钟交了一发T了，发现离散化数组没排序就直接unique了，改完bug，bestcode就炸了。赛后补题，wa了两次，看着代码看了二十分钟，最后发现原来是oj没把题目搬完，交啥都是错的。。。搬完后就一发a了。。太伤心了。

#include<bits/stdc++.h>

#define rep(i,a,b) for(int i=a;i<=b;i++)

#define dep(i,b,a) for(int i=b;i>=a;i--)

#define clr(a,b) memset(a,b,sizeof(a))

#define pb push_back

#define pii pair<int,int >

using namespace std;

typedef long long ll;

ll rd() {

    ll x=,f=;

    char ch=getchar();

    while(ch<''||ch>'') {

        if(ch=='-')f=-;

        ch=getchar();

    }

    while(ch>=''&&ch<='') {

        x=x*+ch-'';

        ch=getchar();

    }

    return x*f;

}

const int maxn=+;

const int inf=0x3f3f3f3f;

struct rc{

    ll x1,x2,y1,y2;

}a[];

double mp[][][];

vector<ll >vx,vy;

ll xa,ya,xb,yb,n,m,num;

struct edge{

    int to;

    double w;

    friend bool operator<(const edge &a,const edge &b){

        return a.w>b.w;

    }

};

priority_queue<edge >q;

vector<edge >ve[];

int getid(int x,int y){

    return (y-)*n+x;

}

bool check(int x,int y){

    if(x<||x>n||y<||y>m)return false;

    return true;

}

double dis[];

void dij(){

    int px1=lower_bound(vx.begin(),vx.end(),xa)-vx.begin()+;

    int px2=lower_bound(vx.begin(),vx.end(),xb)-vx.begin()+;

    int py1=lower_bound(vy.begin(),vy.end(),ya)-vy.begin()+;

    int py2=lower_bound(vy.begin(),vy.end(),yb)-vy.begin()+;

    int id1=getid(px1,py1),id2=getid(px2,py2);

//    printf("id1:%d  id2:%d  n:%d  m:%d px1:%d  py1:%d  px2:%d  py2:%d\n",id1,id2,n,m,px1,py1,px2,py2);

    dis[id1]=;

    q.push({id1,});

    while(!q.empty()){

        edge st=q.top();

        q.pop();

        int u=st.to;

            double w=st.w;

//        printf("u:%d  w:%.4f\n",u,w);

        int si=ve[u].size();

        rep(i,,si-){

            int v=ve[u][i].to;

            if(dis[v]>dis[u]+ve[u][i].w){

                dis[v]=dis[u]+ve[u][i].w;

                q.push({v,dis[v]});

            }

        }

    }

    printf("%.5f\n",dis[id2]);

}

int main(){

    int T;

    cin>>T;

    while(T--){

        cin>>num;

        vx.clear(),vy.clear();

        rep(i,,num){

            a[i].x1=rd();

            a[i].y1=rd();

            a[i].x2=rd();

            a[i].y2=rd();

            vx.pb(a[i].x1),vx.pb(a[i].x2);

            vy.pb(a[i].y1),vy.pb(a[i].y2);

        }

        cin>>xa>>ya>>xb>>yb;

        vx.pb(xa),vx.pb(xb);

        vy.pb(ya),vy.pb(yb);

        sort(vx.begin(),vx.end());

        sort(vy.begin(),vy.end());

        vx.erase(unique(vx.begin(),vx.end()),vx.end());

        vy.erase(unique(vy.begin(),vy.end()),vy.end());

        n=vx.size(),m=vy.size();

        rep(i,,n){

            rep(j,,m){

                rep(k,,)

                mp[i][j][k]=;

                ve[getid(i,j)].clear();

                dis[getid(i,j)]=;

            }

        }

        rep(i,,num){

            int px1=lower_bound(vx.begin(),vx.end(),a[i].x1)-vx.begin()+;

            int px2=lower_bound(vx.begin(),vx.end(),a[i].x2)-vx.begin()+;

            int py1=lower_bound(vy.begin(),vy.end(),a[i].y1)-vy.begin()+;

            int py2=lower_bound(vy.begin(),vy.end(),a[i].y2)-vy.begin()+;

            rep(x,px1+,px2-){

                rep(y,py1+,py2-){

                    mp[x][y][]++;

                    mp[x][y][]++;

                    mp[x][y][]++;

                    mp[x][y][]++;

                }

            }

            rep(x,px1+,px2-){

                int y=py1;

                mp[x][y][]++;

                mp[x][y][]++;

                mp[x][y][]++;

                y=py2;

                mp[x][y][]++;

                mp[x][y][]++;

                mp[x][y][]++;

            }

            rep(y,py1+,py2-){

                int x=px1;

                mp[x][y][]++;

                mp[x][y][]++;

                mp[x][y][]++;

                x=px2;

                mp[x][y][]++;

                mp[x][y][]++;

                mp[x][y][]++;

            }

            mp[px1][py1][]++;

            mp[px1][py1][]++;

            mp[px1][py2][]++;

            mp[px1][py2][]++;

            mp[px2][py1][]++;

            mp[px2][py1][]++;

            mp[px2][py2][]++;

            mp[px2][py2][]++;

        }

        rep(i,,n){

            rep(j,,m){

                int id=getid(i,j);

                if(check(i-,j))ve[id].pb({getid(i-,j),(vx[i-]-vx[i-])/mp[i][j][]});

                if(check(i+,j))ve[id].pb({getid(i+,j),(vx[i]-vx[i-])/mp[i][j][]});

                if(check(i,j-))ve[id].pb({getid(i,j-),(vy[j-]-vy[j-])/mp[i][j][]});

                if(check(i,j+))ve[id].pb({getid(i,j+),(vy[j]-vy[j-])/mp[i][j][]});

            }

        }

        dij();

    }

}

巴特西

2019 年百度之星·程序设计大赛 - 初赛一 C. Mindis 离散化+dijkstra

最新文章

热门文章