dijsktra 80分 wa第一个点 求助大佬qwq
查看原帖
dijsktra 80分 wa第一个点 求助大佬qwq
187407
huangbohan楼主2020/11/1 19:07
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<vector>
#include<string>
#include<map>
#include<queue>
using namespace std;
int N,M;
int x[10000010],y[10000010];
double dis[10000010];
int head[10000010],p,vis[100000010];
struct edge
{
	int To,nex;
	double v;
};
edge e[10000010];
void add(int a,int b,double c)
{
	p++;
	e[p].To=b;
	e[p].v=c;
	e[p].nex=head[a];
	head[a]=p;
}
struct node
{
	double dis;
	int pos;
	bool operator < (const node &x) const
	{
		return dis<x.dis;
	}
};
priority_queue <node> q;
void Dij(int sta)
{
	for(int i=1;i<=N;i++)
	{
		dis[i]=9999999999.0;
		vis[i]=0;
	}
	dis[sta]=0.0;
	q.push((node){0.0,sta});
	while(!q.empty())
	{
		node tmp=q.top();
		q.pop();
		int x=tmp.pos;
		if(vis[x]) continue;
		vis[x]=1;
		int c=head[x];
		while(c)
		{
			int pd=e[c].To;
			if(dis[pd]>dis[x]+e[c].v)
			{
				dis[pd]=dis[x]+e[c].v;
				if(!vis[pd]) q.push((node){dis[pd],pd});
			}
			c=e[c].nex;
		}
	}
}
int main()
{
	scanf("%d",&N);
	for(int i=1;i<=N;i++)
	scanf("%d %d",&x[i],&y[i]);
	scanf("%d",&M);
	for(int i=1;i<=M;i++)
	{
		int u,v;
		scanf("%d %d",&u,&v);
		double w=sqrt( (x[u]-x[v])*(x[u]-x[v]) + (y[u]-y[v])*(y[u]-y[v]) );
		add(u,v,w);
		add(v,u,w);
	}
	int s,T;
	scanf("%d %d",&s,&T);
	Dij(s);
	printf("%.2lf",dis[T]);
	return 0;
}
2020/11/1 19:07
加载中...