救,两个WA一个MLE,Dijkstra
查看原帖
救,两个WA一个MLE,Dijkstra
530570
Firrel_qaq楼主2023/12/22 13:39
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<queue>
using namespace std;
struct node{
	int x,y;
};
struct que{
	double dis;
	int id;
	bool operator <(const que &x)const{
        return x.dis<dis;
    }
};
node z[10005];
double dist(int x1,int y1,int x2,int y2 ){
    double sum,Sum;
    sum = abs(pow(x1 - x2,2) + pow(y1 - y2,2));
    Sum = abs(sqrt(sum));
    return Sum;
}
int n,m,s,e;
double mp[10005][10005];
double vis[10005];
bool white[10005];
double bfs(){
	priority_queue<que> q;
	q.push({0,s});
	while(!q.empty()){
		int t = q.top().id;
		white[t] = 1;
		q.pop();
		for(int i = 1;i <= n;i++){
			if(mp[t][i]){
				vis[i] = min(vis[t] + mp[t][i],vis[i]);
				if(!white[i]) q.push({vis[i],i});
			}
		}
	}
	return vis[e];
}
int main(){
	scanf("%d",&n);
	for(int i = 1;i <= n;i++){
		scanf("%d%d",&z[i].x,&z[i].y);	
		vis[i] = 10000000000;
	}
	scanf("%d",&m);
	for(int i = 1;i <= m;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		double t = dist(z[u].x,z[u].y,z[v].x,z[v].y);
		//printf("%.2f\n",t);
		mp[u][v] = t;
		mp[v][u] = t;
	}
	scanf("%d%d",&s,&e);
	vis[1] = 0;
	double ans = bfs();
	printf("%.2f",ans);
	return 0;
}

2023/12/22 13:39
加载中...