为什么会挂欸?!
奇怪了呢ヾ(•ω•`)o
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10;
int head[N],nex[N],ver[N],idx,f[N*2];
double val[N],dis[N];//链式前向星和计算距离
int x[N],y[N];//记录一下坐标
int n,m,z,s;
bool v[N];
int cnt,flag;
int path[N];//记录路径
double find_dis(int a,int b)
{
return sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));
}//两点之间距离公式
void add(int from,int to,double value)
{
ver[++idx]=to;
val[idx]=value;
nex[idx]=head[from];
head[from]=idx;
f[idx]=from;//存一下这条边的起点方便以后删边用
}
void Dijkstra(int from,int to)//不跑要删的那条边
{
memset(dis,0x3f,sizeof(dis));
priority_queue<pair<int,int>> que;
que.push(make_pair(0,1));
dis[1]=0;
while(!que.empty())
{
int x=que.top().second;//取出节点
que.pop();
if(v[x]) continue;
v[x]=1;
for(int i=head[x];i;i=nex[i])
{
int j=ver[i];
if( (x==from&&j==to)||(x==to&&j==from) ) continue;
//无向边注意双向判断
//是这条边就跳过
//如果不是这条路再更新
if(dis[j] > dis[x]+val[i])
{
dis[j] > dis[x]+val[i];
if(!flag||from==-1&&to==-1)//如果是第一次走就记录路径
{
path[j]=x;
}
que.push(make_pair(-dis[j],j));//dijkstra的模板内容
//如果是用当前的全源最短进行了松弛,那出来的肯定是最短的
}
}
}
}
int main()
{
cin >> n >> m ;
for(int i=1;i<=n;i++)
{
cin >> x[i] >> y [i] ;
}
for(int i=1;i<=m;i++)
{
int a,b;
cin >> a >> b;
double distance=find_dis(a,b);
add(a,b,distance);
add(b,a,distance);//注意无向图双向连边
}
Dijkstra(-1,-1);//先跑一边
flag=1;
double ans=0x3f3f3f3f;
int now=n;
while(path[now]!=0)
{
Dijkstra(path[now],now);//重新跑一边dijkstra,现在dis里面存的是次短路了
ans=min(dis[n],ans);
now=path[now];
}
if(ans==0x3f3f3f3f) cout << -1 << endl;
else cout << ans << endl;
return 0;
}