POJ 3126 Prime Path SPFA
poj path SPFA Prime
2023-09-14 09:09:00 时间
http://poj.org/problem?
id=3126
题目大意:
给你两个四位的素数s和t,要求每次改变一个数字。使得改变后的数字也为素数,求s变化到t的最少变化次数。
思路:
首先求出全部4位素数。
对于两个素数之间,假设仅仅相差一个数字,那么就建立图。(双向)
最后求最短路就可以(能够SPFA也能够BFS)
#include<cstdio> #include<cstring> #include<queue> #include<algorithm> using namespace std; const int MAXN=10000+10; const int INF=0x3ffffff; bool isprimer[MAXN]; int primer[MAXN],num; int head[MAXN],len; struct edge { int to,next; }e[MAXN*10]; void add(int from,int to) { e[len].to=to; e[len].next=head[from]; head[from]=len++; } //推断两个数仅有一个数字不同 bool judge(char *x,char *y) { int cnt=0; for(int i=0;i<4;i++) if(x[i]==y[i]) cnt++; return cnt==3; } int dis[MAXN]; bool vis[MAXN]; int spfa(int s,int t) { for(int i=1000;i<=10000;i++) { dis[i]=INF; vis[i]=0; } dis[s]=0; vis[s]=true; queue<int> q; q.push(s); while(!q.empty()) { int cur=q.front(); q.pop(); for(int i=head[cur];i!=-1;i=e[i].next) { int to=e[i].to; if(dis[cur]+ 1 < dis[to]) { dis[to]=dis[cur]+1; if(!vis[to]) q.push(to); } } } return dis[t]; } int main() { memset(head,-1,sizeof(head)); num=len=0; for(int i=2;i*i<MAXN;i++) { if(!isprimer[i]) for(int j=i;j*i<MAXN;j++) isprimer[i*j]=true; } for(int i=1000;i<10000;i++) if(!isprimer[i]) primer[num++]=i; //printf("%d\n",num); char cur[5],temp[5]; for(int i=0;i<num;i++) { sprintf(cur,"%d",primer[i]); // printf("%s\n",cur); for(int j=i+1;j<num;j++) { sprintf(temp,"%d",primer[j]); if(judge(cur,temp)) { add(primer[j],primer[i]); add(primer[i],primer[j]); } } } int T; scanf("%d",&T); while(T--) { int a,b; scanf("%d%d",&a,&b); if(isprimer[b]) { printf("Impossible\n"); continue; } int ans=spfa(a,b); if(ans==INF) printf("Impossible\n"); else printf("%d\n",ans); } return 0; }
相关文章
- poj1142_poj是什么意思
- POJ 2606 Rabbit hunt 2780 Linearity 1118 Lining Up 解题报告
- POJ PKU 2826 An Easy Problem?! 解题报告
- The Unique MST POJ - 1679 【 最小生成树是否唯一判断 】
- Simple Problem with Integers(POJ 3486)
- 棋盘问题 ( POJ -1321 )(简单DFS)
- Catch That Cow (POJ - 3278)(简单BFS)
- Dungeon Master (POJ - 2251)【 三维 BFS 】
- Prime Path (POJ - 3126 )(BFS)
- Til the Cows Come Home ( POJ 2387) (简单最短路 Dijkstra)
- Subsequence (POJ - 3061)(尺取思想)
- Cash Machine (POJ 1276)(多重背包——二进制优化)
- Linux下修改Path的步骤(linux修改path)
- 深入Linux:更新PATH路径(linux更新path)
- Linux下设置多个Path的方法(linux多个path)
- Linux添加PATH的正确方式(linux加path)
- Oracle安装之路:精准定位Path问题(oracle安装path)
- 路径配置Linux系统中PATH路径的配置(linux系统path)
- Linux系统下设置 PATH 环境变量(linux设置环境变量path)
- Linux 修改 PATH 环境变量指南 (linux修改path环境变量)
- 【Linux恢复PATH:让你的路径重获新生】(linux恢复path)
- 聆听Linux的默认PATH之旅(linux默认path)
- 如何查看Linux系统中的PATH环境变量?(linux查看path)
- 如何使用Linux查看PATH环境变量(linux查看path)
- 深入理解 Linux 中的 Path 路径设置(linux中path)
- Linux 下添加环境变量 PATH 的步骤(linux添加 path)
- Linux修改PATH路径的简单方法(linux更改path)
- 探索Linux的环境变量PATH(linux环境变量path)
- Oracle中Path开启新路(Oracle中path)