源代码如下
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
int w=1,s=0;char ch=getchar();
while(!isdigit(ch)) {if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch)){s=s*10+(ch-'0');ch=getchar();}
return w*s;
}
int h,n;
struct no
{
int y,nxt;
}edge[1000100];
int head[1000100],len;
void add(int x,int y)
{
edge[++len]=(no){y,head[x]};
head[x]=len;
}
struct dian
{
int x,y;
}w[1000100];
double dis(dian a,dian b)
{
return sqrt(1.0*(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int dist[1000100];
bool vis[1000100];
struct noo
{
int v,id;
inline friend operator <(noo qq,noo ww)
{
return qq.v>ww.v;
}
};
priority_queue<noo> q;
void work()
{
memset(dist,0x3f,sizeof dist);
dist[0]=0;
q.push({0,0});
while(q.size())
{
int x=q.top().id;
q.pop();
if(vis[x]) continue;
vis[x]=1;
for(int i=head[x];i;i=edge[i].nxt)
{
int y=edge[i].y;
if(dist[y]>dist[x]+1)
{
dist[y]=dist[x]+1;
q.push({dist[y],y});
}
}
}
}
int main()
{
cin>>h>>n;
for(int i=1;i<=n;i++)
{
w[i].x=read();w[i].y=read();
if(w[i].y<=1000)
{
add(0,i);
}
if(h-w[i].y<1000)
{
add(i,n+1);
}
}
for(int i=1;i<n;i++)
{
for(int j=i+1;j<=n;j++)
{
if(dis(w[i],w[j])<=1000.0)
{
add(i,j);
add(j,i);
}
}
}
work();
cout<<dist[n+1]-1;
return 0;
}
本地编译可以过,但是在洛谷上CE了,请问是为什么?