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;
}
#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) 回帖