POJ 3126

Prime Path

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 10320		Accepted: 5897

Description

The ministers of the cabinet were quite upset by the message from the Chief of Security stating that they would all have to change the four-digit room numbers on their offices.
— It is a matter of security to change such things every now and then, to keep the enemy in the dark.
— But look, I have chosen my number 1033 for good reasons. I am the Prime minister, you know!
— I know, so therefore your new number 8179 is also a prime. You will just have to paste four new digits over the four old ones on your office door.
— No, it’s not that simple. Suppose that I change the first digit to an 8, then the number will read 8033 which is not a prime!
— I see, being the prime minister you cannot stand having a non-prime number on your door even for a few seconds.
— Correct! So I must invent a scheme for going from 1033 to 8179 by a path of prime numbers where only one digit is changed from one prime to the next prime.

Now, the minister of finance, who had been eavesdropping, intervened.
— No unnecessary expenditure, please! I happen to know that the price of a digit is one pound.
— Hmm, in that case I need a computer program to minimize the cost. You don't know some very cheap software gurus, do you?
— In fact, I do. You see, there is this programming contest going on... Help the prime minister to find the cheapest prime path between any two given four-digit primes! The first digit must be nonzero, of course. Here is a solution in the case above.

1033
1733
3733
3739
3779
8779
8179

The cost of this solution is 6 pounds. Note that the digit 1 which got pasted over in step 2 can not be reused in the last step – a new 1 must be purchased.

Input

One line with a positive number: the number of test cases (at most 100). Then for each test case, one line with two numbers separated by a blank. Both numbers are four-digit primes (without leading zeros).

Output

One line for each case, either with a number stating the minimal cost or containing the word Impossible.

Sample Input

Sample Output

6
7
0

Source

Northwestern Europe 2006

水题，对1000 ～ 9999 的素数按照题目要求建边，最后找一条单源最短路即可。

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 #include <vector>
  6 #include <queue>
  7 
  8 using namespace std;
  9 
 10 #define maxn 10005
 11 
 12 struct node {
 13         int d,u;
 14         bool operator < (const node & rhs) const {
 15                 return d > rhs.d;
 16         }
 17 };
 18 int a,b,len = 0;
 19 bool prime[maxn],done[maxn];
 20 int key[maxn],ele[maxn],d[maxn];
 21 vector<int> G[maxn];
 22 
 23 
 24 bool judge(int x,int y) {
 25         int sum = 0;
 26         while(x) {
 27                 sum += (x % 10 == y % 10);
 28                 x /= 10;
 29                 y /= 10;
 30         }
 31 
 32         return sum == 3;
 33 }
 34 void build() {
 35         for(int i = 0; i < len; i++) {
 36                 for(int j = i + 1; j < len; j++) {
 37                         if(judge(ele[i],ele[j])) {
 38                                 //printf("%d %d
",ele[i],ele[j]);
 39                                 G[i].push_back(j);
 40                                 G[j].push_back(i);
 41                         }
 42                 }
 43         }
 44 }
 45 void init() {
 46         for(int i = 3; i <= maxn - 5; i++) {
 47                 prime[i] = i % 2;
 48         }
 49 
 50         prime[2] = 1;
 51 
 52         for(int i = 2; i <=  maxn - 5; i++) {
 53                 if(!prime[i]) continue;
 54                 for(int j = i; j * i <= maxn - 5; j++) {
 55                         prime[j * i] = 0;
 56                 }
 57         }
 58 
 59         for(int i = 1000; i <= 9999; i++) {
 60                 if(prime[i]) {
 61                         ele[len] = i;
 62                         key[i] = len++;
 63                 }
 64         }
 65 
 66         build();
 67 
 68 }
 69 
 70 void dijkstra(int s) {
 71         for(int i = 0; i < len; i++) d[i] = maxn;
 72         d[s] = 0;
 73         memset(done,0,sizeof(done));
 74 
 75         node t;
 76         priority_queue<node> q;
 77         t.d = 0; t.u = s;
 78         q.push(t);
 79 
 80         while(!q.empty()) {
 81                 node x = q.top(); q.pop();
 82                 int u = x.u;
 83                 if(done[u]) continue;
 84                 done[u] = 1;
 85                 for(int i = 0; i < G[u].size(); i++) {
 86                         int v = G[u][i];
 87                         if(d[v] > d[u] + 1) {
 88                                 d[v] = d[u] + 1;
 89                                 t.d = d[v];
 90                                 t.u = v;
 91                                 q.push(t);
 92                         }
 93                 }
 94         }
 95 
 96 }
 97 int main()
 98 {
 99     //freopen("sw.in","r",stdin);
100     //freopen("sw.out","w",stdout);
101 
102     int t;
103     init();
104     scanf("%d",&t);
105 
106     while(t--) {
107             scanf("%d%d",&a,&b);
108             dijkstra(key[a]);
109 
110             if(d[ key[b] ] == maxn) {
111                     printf("Impossible
");
112 
113             } else {
114                     printf("%d
",d[ key[b] ]);
115             }
116 
117     }
118     return 0;
119 }

View Code