测试点1过,但0分,求助:)
查看原帖
测试点1过,但0分,求助:)
640259
hui_du楼主2023/7/25 20:35
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define  dd double
const int N=1e6+10,inf=0x7fffffff;
ll re(){
	ll r=0;bool f=1;char c=getchar();
	for(;!('0'<=c&&c<='9');c=getchar())if(c=='-')f=0;
	for(;'0'<=c&&c<='9';c=getchar())r=(r<<3)+(r<<1)+(c^48);
	return f?r:-r;
}
ll n,m,s,t,to[N],h[N],nt[N],cnt;
dd v[N],d[N];
bool f[N];
struct no{
	dd v;
	ll w;
	friend bool operator < (no a,no b){
		return a.v>b.v;
	}
}u;
struct node{
	ll x,y;
}a[N];
void add(ll i,ll j){
	to[++cnt]=j;
	v[cnt]=sqrt(abs(a[i].x-a[j].x)*abs(a[i].x-a[j].x)+abs(a[i].y-a[j].y)*abs(a[i].y-a[j].y));
	nt[cnt]=h[i];
	h[i]=cnt;
	
	ll t=i;
	i=j;
	j=t;
	
	to[++cnt]=j;
	v[cnt]=sqrt(abs(a[i].x-a[j].x)*abs(a[i].x-a[j].x)+abs(a[i].y-a[j].y)*abs(a[i].y-a[j].y));
	nt[cnt]=h[i];
	h[i]=cnt;
}
priority_queue<no>q;
int main(){
	n=re();
	for(int i=1;i<=n;++i)
		a[i].x=re(),a[i].y=re();
	m=re();
	for(int i=1,a,b;i<=m;++i)
		a=re(),b=re(),add(a,b),d[i]=inf;
	s=re(),t=re();
	d[s]=0;
	u.v=0,u.w=s;
	q.push(u);
	while(!q.empty()){
		ll now=q.top().w;
		q.pop();
		if(f[now])
			continue;
		f[now]=1;
		for(int i=h[now];i;i=nt[i])
			if(d[to[i]]>d[now]+v[i]){
				d[to[i]]=d[now]+v[i];
				u.v=d[to[i]],u.w=to[i],q.push(u);
			}
	}
	printf("%.2llf",d[t]);
}
2023/7/25 20:35
加载中...