Dijkstra(堆优化)20分,求助大佬们帮忙看看
查看原帖
Dijkstra(堆优化)20分,求助大佬们帮忙看看
89398
WatT_T楼主2018/8/26 15:36
#include<map>
#include<cmath>
#include<queue>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<fstream>
#include<iostream>
#include<algorithm>
#define re register
#define ll long long
using namespace std;
int n,m,s,t;
int cnt=0,first[20000];
const int inf=0x7fff;
double dis[20000];
struct gg{
	int x;
	int y;
}a[20000];
struct kk{
	int v;
	double w;
	int next;
}lin[20000];
inline void lianbiao(int u,int v,double w){//邻接表储存
	lin[++cnt].v=v;
	lin[cnt].w=w;
	lin[cnt].next=first[u];
	first[u]=cnt;
}
struct node{
	int u;
	double len;
	bool operator <(const node& rhs) const{
		return len>rhs.len;
	}
};
inline void Dijkstra(){
//Dijkstra(堆优化)
	for(int i=1;i<=n;i++)dis[i]=inf;
	dis[s]=0;
	priority_queue<node> q;
	q.push(node{s,dis[s]});
	while(q.size()){
		node k=q.top();
		q.pop();
		int u=k.u;;
		double len=k.len;
		if(len!=dis[u])continue;
		for(int i=first[u];i;i=lin[i].next){
			int v=lin[i].v;
			double w=lin[i].w;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				q.push(node{v,dis[v]});
			}
		}
	}
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&a[i].x,&a[i].y);
	}
	scanf("%d",&m);
	double k;
	int l,r;
	for(int i=1;i<=n;i++){
		scanf("%d%d",&l,&r);
		int xx=(a[l].x-a[r].x);
		int yy=(a[l].y-a[r].y);
		k=sqrt(xx*xx+yy*yy);
		lianbiao(l,r,k);
		lianbiao(r,l,k);
	}
	scanf("%d%d",&s,&t);
	Dijkstra();
	printf("%.2lf",dis[t]);
}
2018/8/26 15:36
加载中...