【求助】dj堆优化WA第一个点80pts
查看原帖
【求助】dj堆优化WA第一个点80pts
807221
xiaopig114514楼主2024/7/19 10:38
#include <bits/stdc++.h>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <queue>
#define int long long
#define N 114
using namespace std;
pair <int, int> a[N];
double dis[N];
bool vis[N];
int n, m, s, t;
struct node
{
	int to;
	double dist;
};
vector <node> x[N];
priority_queue< pair <double, int> > q;
void read() 
{
	cin >> n;
	for (int i = 1; i <= n; i ++) 
	{
		cin >> a[i].first >> a[i].second;
	}
    cin >> m;
	for (; m; m --) 
	{
		int xx, y;
		cin >> xx >> y;
		double dist = (a[xx].first - a[y].first)*(a[xx].first - a[y].first)+(a[xx].second-a[y].second)*(a[xx].second-a[y].second);
		dist = sqrt(dist);
		x[xx].push_back((node){y, dist});
		x[y].push_back((node){xx, dist});
        //cout << dist << '*';
	}
	cin >> s >> t;
}
void calc() 
{
    //memset(dis, -1, sizeof(dis));
    for (int i = 1; i <= n; i ++) 
    {
        dis[i] = 1145141919910;
    }
	pair <double, int> qq;
	qq.first = 0;
	qq.second = s;
	dis[s] = 0;
	q.push(qq);
	while (q.size()) 
	{
		pair<double,int>tp=q.top();
		q.pop();
        if (vis[tp.second]) continue;
		vis[tp.second] = 1;
		for(auto ss: x[tp.second]) 
		{
            
			
				if(dis[ss.to]>dis[tp.second]+ss.dist)dis[ss.to] = dis[tp.second]+ss.dist;
				if(!vis[ss.to])
			{qq.first = dis[ss.to];
                //cout << dis[ss.to]<<'.';
				qq.second = ss.to;
				q.push(qq);
			}
		}
	}
}
void out() 
{
	cout <<fixed << setprecision(2)<< dis[t] << endl;
}
signed main() 
{
	read();
	calc();
	out();
	return 0;
}
2024/7/19 10:38
加载中...