poj3126 Prime Path

方法一

由于四位数的素数仅有 \(1061\) 个，因此可以预处理所有的四位素数，每两个素数之间只有一位不同则有边，由此建出一个无向图。预处理后便成了裸的图上 \(bfs\) 。

/**
* poj3126 Prime Path
* 四位数的素数仅1061个
* prime[169] = 1009, prime[1229] = 9973;
*/

#include <cstdio>
#include <queue>
#include <iostream>
#include <cstring>
using namespace std;

const int N = 1e4+8, M = 1234;
bool vis[N];
int prime[M], mp[10000];
vector<int> G[M];

int n = 1061, start = 169;

void getPrime()
{
    int &cnt = prime[0];
    for (int i = 2; i < N; ++i) {
        if (!vis[i]) prime[++cnt] = i;
        for (int j = 1; j <= cnt && i * prime[j] < N; ++j) {
            vis[i * prime[j]] = 1;
            if (i % prime[j] == 0) break;
        }
    }
}

void check(int i, int j)
{
    int x = prime[i], y = prime[j];
    int cnt = 0;
    while (x) {
        cnt += x%10 != y%10;
        x /= 10, y /= 10;
    }
    x = prime[i], y = prime[j];
    if (cnt == 1) {
        G[i].push_back(j);
        G[j].push_back(i);
    }
}

struct node{int x, step;};
int bfs(int a, int b)
{
    memset(vis, 0, sizeof vis);
    queue<node> Q;
    Q.push(node{a,0});
    vis[a] = 1;
    while (!Q.empty()) {
        node t = Q.front(); Q.pop();
        if (t.x == b) return t.step;
        for (int i = 0; i < G[t.x].size(); ++i) {
            int k = G[t.x][i];
            if (vis[k]) continue;
            Q.push(node{k, t.step+1});
            vis[k] = 1;  // 第一次没加这句TLE，太菜了！
        }
    }
    return -1;
}

int main()
{
    getPrime();

    for (int i = 1; i <= n; ++i) {
        prime[i] = prime[start+i-1];
        mp[ prime[i] ] = i;
    }

    // 建图
    for (int i = 1; i <= n; ++i) {
        for (int j = i+1; j <= n; ++j) {
            check(i, j);
        }
    }

    int T;
    cin >> T;
    while (T--) {
        int x, y;
        cin >> x >> y;
        x = mp[x], y = mp[y];
        int ans = bfs(x, y);
        if (ans == -1) puts("Impossible");
        else cout << ans << endl;
    }


    return 0;
}

方法二

不建图，求出素数表后直接 \(bfs\) ， \(bfs\) 时每次改变当前素数的各位数字得到下一个待访问的素数。代码就没写了。。

poj3126 Prime Path

原文：https://www.cnblogs.com/zbhfz/p/14315085.html