样例不过,求调
查看原帖
样例不过,求调
1320239
CSZ7943楼主2025/1/18 11:16
#include<iostream>
#include<cstring>
#include<queue>
#include<cmath>
#include<cstdio>
using namespace std;
int n,m,s,t;
struct node{
	int v;
	double w;
	int nxt;
}g[500005];
int head[500005];
int num;
double d[10005];
int vis[10005];
queue<int> q;
int cnt[10005];
int x[10005];
int y[10005];
double dis(int x1,int y1,int x2,int y2){
	return sqrt(abs(x1-x2)*abs(x1-x2)+abs(y1-y2)*abs(y1-y2));
}
void add(int u,int v,int w){
	g[++num].nxt=head[u];
	g[num].v=v;
	g[num].w=w;
	head[u]=num;
}
void spfa(){
	for(int i=1;i<=n;i++){
		d[i]=1000000000.0;
	}
	memset(vis,0,sizeof(vis));
	int u;
	q.push(s);
	d[s]=0;
	vis[s]=1;
	while(!q.empty()){
		u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=head[u];i;i=g[i].nxt){
			int v=g[i].v;
			double w=g[i].w;
			if(d[v]>d[u]+w){
				d[v]=d[u]+w;
				if(!vis[v]){
					vis[v]=1;
//					if(cnt[v]++>=n){
//						cout<<-1;
//						return 0;
//					}
					q.push(v);
				}
			}
		}
	}
	printf("%.2f",d[t]);
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>x[i]>>y[i];
	}
	cin>>m;
	while(m--){
		int a,b;
		cin>>a>>b;
		add(a,b,dis(x[a],y[a],x[b],y[b]));
		add(b,a,dis(x[a],y[a],x[b],y[b]));
	}
	cin>>s>>t;
	spfa();
	return 0;
}
2025/1/18 11:16
加载中...