玄关求调呜呜呜(妹妹码风良好)
查看原帖
玄关求调呜呜呜(妹妹码风良好)
1062132
Danubius楼主2024/9/12 11:44

为什么会挂欸?!

奇怪了呢ヾ(•ω•`)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;
}

2024/9/12 11:44
加载中...