[BOJ 14431] 소수마을

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

해당 문제의 경우 점의 거리가 소수일 경우 움직일 수 있고, 시작점에서 도착점으로 최소의 경로로 이동하는 문제이다.

문제의 가장 큰 핵심은 먼저 소수들을 에라토스테네스를 이용하여 먼저 구하고 각 정점들이 소수인 거리일 때 각 점들을 이어주고 다익스트라를 수행하면 된다.

모든 정점을 이어준다음 판별한다고 생각을 처음 했었는데 ... ㅋㅋ...

#include<iostream>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<utility>
#include<vector>
#include<cstring>
#include<queue>
#include<cmath>
#include<math.h>
#define INF 1e9
typedef long long ll;
 
using namespace std;
 
int n,xp1,xp2,yp1,yp2,dist[11111];
bool prime[11111];
 
void eratos(){
    for (int i = 2; (i*i) <= 10000; i++){
        if (prime[i]){                     // 이전 수의 배수였을 가능성을 제외
            for (int j = i*i; j <= 10000; j += i){ // i*i를 통해 중복연산 제외
                prime[j] = false;
            }
        }
    }
}
 
 
int main(){
    vector<pair<int,int>> tmp;
    vector<vector<pair<int,int>>> v;
    memset(prime,true,sizeof(prime));
    eratos();
    
    prime[1] = false;
    
    cin >> xp1>>yp1>>xp2>>yp2>>n;
    
    tmp.push_back({xp1,yp1});
    tmp.push_back({xp2,yp2});
    v.resize(n+3);
    
    for(int i=0;i<n;i++){
        int a,b;
        cin >> a>>b;
        tmp.push_back({a,b});
    }
    for(int i=0;i<n+2;i++){
        dist[i] = INF;
        int q = tmp[i].first;
        int w = tmp[i].second;
        for(int j=i+1;j<n+2;j++){
            int e =tmp[j].first;
            int r = tmp[j].second;
            int dist =sqrt(pow(q - e, 2) + pow(w- r, 2));
            if(prime[dist]){
                v[i].push_back({j,dist});
                v[j].push_back({i,dist});
            }
        }
    }
    queue<int> q;
    q.push(0);
    dist[0] = 0;
    
    while(!q.empty()){
        int pos = q.front();
        q.pop();
        
        for(int i=0;i<v[pos].size();i++){
            int next = v[pos][i].first;
            if(dist[next] > dist[pos]+v[pos][i].second){
                dist[next] = dist[pos]+v[pos][i].second;
                q.push(next);
            }
        }
    }
    
    if(dist[1] == INF){
        printf("-1\n");
    }else{
        printf("%d\n" , dist[1]);
    }
    
}