[백준]소수마을(14431)

문제 링크 : [백준]소수마을(14431)

문제 설명

소수마을과 A마을, N개의 마을들의 좌표가 주어집니다.
소수마을에서 A마을까지 이동하려고 하는데, 이동 할 때는, 이동거리가 소수인 경우에만 이동 할 수 있습니다.
이동거리는 두 마을간의 이동 거리이며, 소수점은 버립니다.
소수마을에서 A마을까지의 최단거리를 구하세요.

입력

P_x P_y A_x A_y(소수마을의 좌표, 마을의 좌표)
N(마을의 갯수, 1 <= N <= 4,000)
X_i Y_i(마을의 좌표)
(모든 좌표의 절대값을 3,000 이하입니다.)

1 2 5 4
2
4 1
6 2

출력

6

카테고리

#다익스트라 #에라토스테네스의 체

시간 복잡도 상한

O(N * N * logN)

해결 방법

1. 마을간의 엣지만 구할 수 있다면 다익스트라로 풀 수 있는 문제입니다.
2. 마을간의 엣지를 구하기 위해서는 마을간 이동거리가 소수인지 판별해야 합니다.
3. 소수 판별을 위해서 에라토스테네스의 체를 이용하여 마을의 이동거리의 최대거리까지 소수 여부를 판별합니다.
4. 모든 마을간의 거리를 구하고, 그 거리가 소수라면 인접리스트에 정보를 넣어 모든 간선 정보를 만듭니다.
5. 간선 정보들을 다 만들었다면 다익스트라를 통해 최단거리를 구합니다.

시간복잡도

O(N * N * logN)

코드

#include<cstdio>
#include<math.h>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
typedef pair<int,int>P;
int n,i,j,k,d[4002][2],p[9000]={1,1},e[4002];
vector<P>v[4002];
priority_queue<P,vector<P>,greater<P>>q;
int x(int a){return a*a;}
int main(){
    for(i=2;i*i<8500;i++)if(!p[i])for(j=2;j*i<8500;j++)p[i*j]=1;
    scanf("%d%d%d%d",d[0],d[0]+1,d[1],d[1]+1);
    scanf("%d",&n);
    n+=2;
    for(i=2;i<n;i++)scanf("%d%d",d[i],d[i]+1);
    for(i=0;i<n;i++)for(j=i+1;j<n;j++){
        k=sqrt(x(d[i][0]-d[j][0])+x(d[i][1]-d[j][1]));
        if(!p[k])v[i].push_back({k,j}),v[j].push_back({k,i});
    }
    q.push({0,0});
    while(!q.empty()){
        P c=q.top();q.pop();
        if(c.second==1){
            printf("%d",c.first);
            return 0;
        }
        if(e[c.second])continue;
        e[c.second]=1;
        for(P x:v[c.second])if(!e[x.second])q.push({c.first+x.first,x.second});
    }
    printf("-1");
}