求助40pts!玄关!dijkstra!!!
查看原帖
求助40pts!玄关!dijkstra!!!
537218
2012zxt楼主2023/10/1 15:36
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int n;
long double dis[N];
bool vis[N];
struct node{
	int id;
	double w;
	bool operator<(const node&x) const{
		return w>x.w;
	}
};
struct ed{
	int x,y;
}a[100005];
vector<node> nbr[N];
void dijk(int s){
	memset(vis,0,sizeof(vis));
	priority_queue<node> pq; 
	for(int i=1;i<=n;i++)
		dis[i]=1e20;
	dis[s]=0;
	node start={s,0};    
	pq.push(start);
	while(!pq.empty()){
		node now=pq.top();
		pq.pop();
		int cur=now.id;
		if(vis[cur])
			continue; 
		vis[cur]=1;
		for(int j=0;j<nbr[cur].size();j++){
			int nxt=nbr[cur][j].id;
			double w=nbr[cur][j].w;
			if(dis[cur]<dis[nxt]-w){
				dis[nxt]=dis[cur]+w; 
				node tmp={nxt,dis[nxt]};
				pq.push(tmp);
			}
		}
	}
	return ;
}
double help(int x1,int y1,int x2,int y2){
	double len=(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
	return sqrt(len); 
}
signed main(){
	int m,s;
	cin>>n;
	for(int i=1;i<=n;i++){
		int x,y;
		cin>>x>>y;
		a[i].x=x,a[i].y=y;
	}
	cin>>m;
	for(int i=1;i<=m;i++){
		int t1,t2;
		cin>>t1>>t2;
		double len=help(a[t1].x,a[t1].y,a[t2].x,a[t2].y);
		nbr[t1].push_back((node){t2,len});
	}
	int t;
	cin>>s>>t;
	dijk(s);
	cout<<fixed<<setprecision(2)<<dis[t];
	return 0;
}

看了数据,发现好像我前三个点输出极大值,也就是没找到路径

2023/10/1 15:36
加载中...