[ boj : 14431 ] 소수 마을

https://www.acmicpc.net/problem/14431

14431번: 소수마을

문제 : 서로간의 거리가 소수이어야지만 건널수 있습니다. 이때 시작점에서 도착점 까지 도착할 수 있는 가장 최단거리를 구하세요

해설 : 일단 핵심은 다익스트라 문제입니다. 다만 서로다른 정점간의 간선의 가중치가 소수인 애들만 골라서 연결을 시켜주면 됩니다. 에라토스체네스의 체를 사용해도 괜찮고 O(sqrt(n))의 시간복잡도를 사용하여 소수를 판정해도 괜찮습니다. 주의할 점은 0과1은 소수가 아니니 간선에 추가시켜주면 안됩니다.

#include<bits/stdc++.h>

using namespace std;

struct info {
	int to, weight;
	bool operator<(const info& cur) const {
		return weight > cur.weight;
	}
};

int n;
int a1, b1, a2, b2;
vector<pair<int, int>> v;
vector<info> adj[4010];

bool sosu(int x);
int djik();
int get_distance(int x, int y, int s, int e);

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> a1 >> b1 >> a2 >> b2 >> n;
	v.push_back({ a1,b1 });

	int a, b;
	for (int i = 0; i < n; i++) {
		cin >> a >> b;
		v.push_back({ a,b });
	}
	v.push_back({ a2,b2 });
	for (int i = 0; i < v.size(); i++)
		for (int j = i + 1; j < v.size(); j++) {
			//if (i == 0 && j == v.size() - 1)continue;
			int dis = get_distance(v[i].first, v[i].second, v[j].first, v[j].second);
			if (!sosu(dis)) continue;
			adj[i].push_back({ j,dis });
			adj[j].push_back({ i,dis });
		}
	cout<<djik();
	return 0;
}
bool sosu(int x)
{
	if (x == 1 || x==0)return false;
	for (int i = 2; i * i <= x; i++)
		if (x % i == 0)
			return false;
	return true;
}
int djik()
{
	int distance[4010];
	for (int i = 0; i < n + 2; i++)distance[i] = (int)1e9;
	priority_queue<info> pq;
	pq.push({ 0,0 });
	distance[0] = 0;

	while (!pq.empty())
	{
		info cur = pq.top();
		pq.pop();

		if (distance[cur.to] < cur.weight)continue;

		for (int i = 0; i<adj[cur.to].size(); i++) {
			int next_to = adj[cur.to][i].to;
			int next_weight = adj[cur.to][i].weight;
			if (distance[next_to] > distance[cur.to] + next_weight) {
				distance[next_to] = distance[cur.to] + next_weight;
				pq.push({ next_to,distance[next_to] });
			}
		}
	}
	if (distance[n + 1] != (int)1e9)return distance[n + 1];
	else return -1;
}
int get_distance(int x, int y, int s, int e)
{
	int dis = (abs((x - s)) * abs((x - s))) + (abs((y - e)) * abs((y - e)));
	return (int)sqrt(dis);
}