3126-Prime Path

問題（外部リンク）

3126 -- Prime Path

実装の概要

それぞれの素数をグラフの頂点と考え、ある特定の桁だけ数字を変えれば良い場合は距離を1として初期化します。
その後はある頂点から別の頂点までの最短距離を求める問題と考えることができます。ワーシャルフロイド法では流石に間に合わないこと、テストケースが100個しかないことからその都度ダイクストラ法を用いて計算します。
優先度付きキューを用いたダイクストラ法であれば十分間に合います。
なお、今回の問題では入力だけでなく途中の数字も4桁と仮定して構いません。

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {

		@SuppressWarnings("unchecked")
        ArrayList<Edge> edges[] = new ArrayList[10000];

		for(int i = 0; i < 10000; i++){
            if(edges[i] == null){
                edges[i] = new ArrayList<Edge>();
            }
        }

		PrimeNumberGenerator pg = new PrimeNumberGenerator();

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		for(int i = 1000; i < 10000; i++){
			if(!pg.isPrime(i)){
				continue;
			}
			//iから1の位だけを変えたもののパスを作る
			for(int j = 1 ; j <= 9 - i%10; j++){
				int tmp = i + j;
				if(pg.isPrime(tmp)){
					edges[i].add( new Edge(tmp, 1));
					edges[tmp].add( new Edge(i, 1));
				}
			}

			//iから10の位だけを変えたもののパスを作る
			for(int j = 1 ; j <= 9 - (i/10)%10; j++){
				int tmp = i + j*10;
				if(pg.isPrime(tmp)){
					edges[i].add( new Edge(tmp, 1));
					edges[tmp].add( new Edge(i, 1));
				}
			}

			//iから100の位だけを変えたもののパスを作る
			for(int j = 1 ; j <= 9 - (i/100)%10; j++){
				int tmp = i + j*100;
				if(pg.isPrime(tmp)){
					edges[i].add( new Edge(tmp, 1));
					edges[tmp].add( new Edge(i, 1));
				}
			}

			//iから1000の位だけを変えたもののパスを作る
			for(int j = 1 ; j <= 9 - (i/1000)%10; j++){
				int tmp = i + j*1000;
				if(pg.isPrime(tmp)){
					edges[i].add( new Edge(tmp, 1));
					edges[tmp].add( new Edge(i, 1));
				}
			}
		}

		int n = Integer.parseInt(br.readLine());

		for(int i = 0; i < n; i++){
			String[] tmpArray = br.readLine().split(" ");

			int a = Integer.parseInt(tmpArray[0]);
			int b = Integer.parseInt(tmpArray[1]);

			int[] result = dijkstra(edges, a, 10000);

			if(result[b] != INF){
				System.out.println(result[b]);
			}
			else {
				System.out.println("Impossible");
			}
		}

	}

	static final int INF = Integer.MAX_VALUE;
	//ダイクストラ法
    static int[] dijkstra(ArrayList<Edge>[] edges, int s, int n){

        PriorityQueue<Distance> que = new PriorityQueue<Distance>();
        int[] dist = new int[n];

        Arrays.fill(dist, INF);
        dist[s] = 0;
        que.add(new Distance(0, s));

        while(!que.isEmpty()){
            Distance tmpDist = que.poll();
            int tmpV = tmpDist.id;

            if(dist[tmpV] < tmpDist.dist){
                continue;
            }
            for(int i = 0; i < edges[tmpV].size() ; i++){
                Edge e = (Edge) edges[tmpV].get(i);
                if(dist[e.to] > dist[tmpV] + e.cost){
                    dist[e.to] = dist[tmpV] + e.cost;
                    que.add(new Distance(dist[e.to], e.to));
                }
            }
        }

        return dist;
    }

}

//ダイクストラ法に用いるためのクラス
class Distance implements Comparable<Distance>{
    int dist;
    int id;

    Distance(int dist, int id){
        this.dist = dist;
        this.id = id;
    }

    @Override
    public int compareTo(Distance d) {
        return this.dist - d.dist;
    }
}

//ダイクストラ法に用いるためのクラス
class Edge {
    int to;
    int cost;

    Edge(int to, int cost){
        this.to = to;
        this.cost = cost;
    }
}

//素数テーブルを生成するためのクラス
class PrimeNumberGenerator {
    private boolean[] isPrime= new boolean[10000];

    public PrimeNumberGenerator() {
        Arrays.fill(isPrime, true);

        isPrime[0] = false;
        isPrime[1] = false;
        isPrime[2] = true;

        for(int i = 3; i <= 9999 ; i++){
            if(i % 2 == 0){
                isPrime[i] = false;
                continue;
            }

            if(isPrime[i] == false){
                continue;
            }

            for(int j = i * 2; j <= 9999; j += i){
                isPrime[j] = false;
            }
        }
    }

    public boolean isPrime(int index){
        return isPrime[index];
    }
}