竞赛讨论区 > 牛客国庆集训派对Day1 L题 nlogn不能A?
头像
metaphysics
发布于 2018-10-02 11:19
+ 关注

牛客国庆集训派对Day1 L题 nlogn不能A?

L题
我用优先队列优化的dijkstra居然wa了
优化的dijkstra算法我在dijkstra模板题ac了
改成了原版O(n^2)dijkstra才过的
谁能解释一下
代码如下:

#include <iostream>
#include<queue>
#include<cmath>
using namespace std;
const int mxm=1e3+10;
int head[mxm]={0};
int p=0;
struct circle{
    double x,y,r;
}cir[mxm];
struct Edge{
    int to,next;
    double w;
}e[mxm<<1];
struct node{
    int id;
    double diss;
    node(int _id,double _diss){
        id=_id;
        diss=_diss;
    }
    bool operator<(const node& o)const{
        return diss<o.diss;
    }
};
int n;
double dis[mxm];
double a,b,c1,c2,det;
void add(int u,int v,double w){
    e[++p].w=w;
    e[p].to=v;
    e[p].next=head[u];
    head[u]=p;
}
double cal(int i,int j){
    double res= sqrt((cir[i].x-cir[j].x)*(cir[i].x-cir[j].x)+(cir[i].y-cir[j].y)*(cir[i].y-cir[j].y))-cir[i].r-cir[j].r;
    if(res<0){
        return 0;
    }else{
        return res;
    }
}
void dijkstra(int u){
    for(int i=1;i<=n+1;i++){
        dis[i]=2e9;
    }
    dis[0]=0;
    priority_queue<node> qu;
    qu.push(node(u,0));
    while(!qu.empty()){
        node k=qu.top();
        qu.pop();
        for(int i=head[k.id];i;i=e[i].next){
            int xl=e[i].to;
            if(dis[xl]>dis[k.id]+e[i].w){
                dis[xl]=dis[k.id]+e[i].w;
                qu.push(node(xl,dis[xl]));
            }
        }
    }
}
int main() {
    cin>>n>>a>>b>>c1>>c2;
    det=sqrt(a*a+b*b);
    for(int i=1;i<=n;i++){
        cin>>cir[i].x>>cir[i].y>>cir[i].r;
    }
    double temp;
    temp=abs(c1-c2)/det;
    add(0,n+1,temp);
    add(n+1,0,temp);
    for(int i=1;i<=n;i++){
        temp=abs(a*cir[i].x+b*cir[i].y+c1)/det-cir[i].r;
        if(temp<0)temp=0;
        add(0,i,temp);
        add(i,0,temp);
        temp=abs(a*cir[i].x+b*cir[i].y+c2)/det-cir[i].r;
        if(temp<0)temp=0;
        add(n+1,i,temp);
        add(i,n+1,temp);
    }
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            temp=cal(i,j);
            add(i,j,temp);
            add(j,i,temp);
        }
    }
    dijkstra(0);
    cout<<dis[n+1]<<endl;
    return 0;
}

全部评论

(1) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐