求助大佬,调了半天,样例都对,其他测试数据都是输出0
查看原帖
求助大佬,调了半天,样例都对,其他测试数据都是输出0
473710
hmr26108楼主2022/1/23 20:21
#include<bits/stdc++.h>
#define INF 2147480000.0
#define maxn 20100
using namespace std;
struct node{
	int next ,v;
	double c;
}e[maxn<<1];
struct que{
	double dis;
	int u;
	bool operator <(const que a) const{
		return dis>a.dis;
	}
};
int tot,h[maxn],vis[maxn];
double dis[maxn],sum=0.0;
int n,m;
struct Node{
	int x,y;
}a[maxn];
void add(int u,int v,double c){
	tot++;
	e[tot].c=c;
	e[tot].v=v;
	e[tot].next=h[u];
	h[u]=tot;
}
void dijkstra(){
	int cnt=0;
	priority_queue<que> q;
	for(int i=1;i<=n;i++) dis[i]=INF;
	memset (vis,0,sizeof(vis));
	dis[1]=0.0;
	q.push(que{0.0,1});
	while(!q.empty()&&cnt<n){
		que now=q.top();
		q.pop();
		int u=now.u;
		if(vis[u]) continue ;
		vis[u]=1;
		//sum+=now.dis;
		cnt++;
		for(int i=h[u];i;i=e[i].next){
			int v=e[i].v;
			if(vis[v]) continue;
			if(dis[v]>e[i].c){
				dis[v]=e[i].c;
				q.push(que{dis[v],v});
			}  
		}
	}
}
int main()
{
	//freopen("P2872_2(1).in","r",stdin);
	//freopen("ans.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&a[i].x,&a[i].y);
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			double t;
			t=(double)(sqrt((double)(a[i].x-a[j].x)*(double)(a[i].x-a[j].x)+(double)(a[i].y-a[j].y)*(double)(a[i].y-a[j].y)));
			//printf("%lf\n",t);
			add(i,j,t);
		}
	}
	for(int i=1;i<=m;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		add(u,v,0.0); 
	}
	dijkstra();
	for(int i=1;i<=n;i++) /*printf("%lf\n",dis[i])*/sum+=dis[i];
	printf("%.2lf",sum);
	return 0;
}
2022/1/23 20:21
加载中...