为什么只A了后两个点 前面的WA了(迪杰斯特拉+堆优化)
查看原帖
为什么只A了后两个点 前面的WA了(迪杰斯特拉+堆优化)
386737
Mei_Misaki楼主2022/1/19 16:02
#include<bits/stdc++.h> 
using namespace std ;
priority_queue<pair<double,int> > q;  
vector<pair<int,double> > G[500005];  
int n,m,s,z,mm=0;  
double dis[105];
struct node{
	int x,y;
}a[105];  
double disnum(int x1,int x2,int y1,int y2){
	return sqrt(abs(x1-x2)*abs(x1-x2)+abs(y1-y2)*abs(y1-y2));
}
void dijk(int s){
	for(int i=1;i<=n;i++)dis[i]=1e9; 
	dis[s]=0; 
	q.push(make_pair(0,s));  
	while(!q.empty()){
		pair<double,int> t=q.top(); 
		q.pop(); 
		int d=-t.first,x=t.second; 
		if(d!=dis[x])continue; 
		for(int i=0;i<G[x].size();i++){
			int y=G[x][i].first;
			if(dis[y]>dis[x]+G[x][i].second){
				dis[y]=dis[x]+G[x][i].second; 
				q.push(make_pair(-dis[y],y));
			}  
		}
	}
}
int main(){
	cin>>n;  
	for(int i=1;i<=n;i++)
		cin>>a[i].x>>a[i].y;
	cin>>m; 
	for(int i=1;i<=m;i++){
		int f,t; 
		double w; 
		cin>>f>>t;  
		w=disnum(a[f].x,a[t].x,a[f].y,a[t].y);  
		G[f].push_back(make_pair(t,w)); 
		G[t].push_back(make_pair(f,w)); 
	}
	cin>>s>>z;  
	dijk(s);
	printf("%.2f",dis[z]);
	return 0;
} 
2022/1/19 16:02
加载中...