14431번: 소수마을

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

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
int n, x[4002], y[4002], xx, yy, dis[4002];
int main() {
    scanf("%d%d%d%d%d", x, y, &xx, &yy, &n);
    for (int i = 1; i <= n; i++) scanf("%d%d", x + i, y + i);
    x[n + 1] = xx;
    y[n + 1] = yy;
    for (int i = 1; i <= n + 1; i++) dis[i] = 2e9;
    priority_queue<pair<int, int> > pq;
    pq.push({ 0,0 });
    while (!pq.empty()) {
        int h = pq.top().second, tdis = -pq.top().first;
        pq.pop();
        if (dis[h] ^ tdis) continue;
        for (int i = 0; i <= n + 1; i++) {
            int d = hypot(x[i] - x[h], y[i] - y[h]), ck = 0;
            for (int j = 2; j*j <= d; j++) if (d%j == 0) {
                ck = 1;
                break;
            }
            if (!ck&&dis[i]>tdis + d) {
                dis[i] = tdis + d;
                pq.push({ -dis[i],i });
            }
        }
    }
    printf("%d", dis[n + 1] < 1e9 ? dis[n + 1] : -1);
    return 0;
}