大佬求调!
查看原帖
大佬求调!
326254
LonginusMonkey楼主2022/8/20 13:23

第四个点老是错,太离谱了!

萌新求助!

#include<bits/stdc++.h>
#define int long long
#define inf 1e10
using namespace std;
struct node{
	int index;
	double data;
};
int x[3010], y[3010], r[3010];
double dis[3010], vis[3010];
double mp[3010][3010];
int n; // n <= 1000 直接连边 
void Dijkstra(int s) {
	for(int i=0; i<=n+11; ++i) {
		dis[i] = 2147483647;
	}
	dis[s] = 0;
	priority_queue<pair<double,int> > que;
	que.push({0,s});
	while(!que.empty()) {
		pair<int,int> temp = que.top(); que.pop();
//		cout << temp.second << " " << temp.first << endl;
		if(vis[temp.second]){
			continue;
		}
		vis[temp.second] = 1;
		for(int i=0; i<=n+1; ++i) {
			if(!vis[i]) {
				if(dis[temp.second] + mp[temp.second][i] < dis[i]) {
					dis[i] = dis[temp.second] + mp[temp.second][i];
					que.push({-dis[i], i});
				}
			}
		}
	}
}
signed main() {
	double xs, ys, xt, yt;
	cin >> xs >> ys >> xt >> yt;
	x[0] = xs, y[0] = ys;
	cin >> n;
	x[n+1] = xt, y[n+1] = yt;
	r[0] = r[n+1] = 0;
	for(int i=1; i<=n; ++i) {
		cin >> x[i] >> y[i] >> r[i];
	}
	for(int i=0; i<=n+1; ++i) {
		for(int j=0; j<=n+1; ++j) {
			double l = sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
			if(l <= r[i]+r[j]) {
				mp[i][j] = 0;
			}
			else
			{
				mp[i][j] = l - r[i] - r[j];
			}
		}
	}
	Dijkstra(0);
	printf("%.10lf", dis[n+1]);
	return 0;
}
2022/8/20 13:23
加载中...