求助,WA第一个
查看原帖
求助,WA第一个
672757
封禁用户楼主2024/8/27 15:48
#include<bits/stdc++.h>
using namespace std;
int st,en,n,m;
struct dian
{
	int a,b;
}nn[105];
bool bi[105][105];
struct di
{
	int x;
	double w;
};
double s;
bool vi[105];
void bfs()
{
	di no,ne;
	queue<di>lj;
	no.x=st;
	no.w=0.0;
	lj.push(no);
	while(1)
	{
		if(lj.empty())
		{
			break;
		}
		no=lj.front();
		lj.pop();
		if(no.x==en)
		{
			s=no.w;
			break;
		}
		for(int i=1;i<=n;i++)
		{
			if(i==no.x)
			{
				continue;
			}
			if(bi[no.x][i]&&!vi[i])
			{
				ne.x=i;
				vi[i]=1;
				ne.w=no.w+double(sqrt(pow((nn[no.x].a-nn[i].a),2)+pow((nn[no.x].b-nn[i].b),2)));
				lj.push(ne);
			}
		}
	}
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>nn[i].a>>nn[i].b;
	}
	cin>>m;
	for(int a,b,i=1;i<=m;i++)
	{
		cin>>a>>b;
		bi[a][b]=bi[b][a]=1;
	}
	cin>>st>>en;
	bfs();
	printf("%.2lf",s);
	return 0;
 } 
2024/8/27 15:48
加载中...