POJ3126 Prime Path 素数-程序员宅基地

技术标签: 算法  poj  素数  algorithm  

         这题先将10000以内的素数都找出来,然后在满足条件的每对素数连上一个权为1的边,接着用dijkstra计算一下最短路就可以。
#ifndef HEAD
#include <stdio.h>
#include <vector>
#include <math.h>
#include <string.h>
#include <string>
#include <iostream>
#include <queue>
#include <list>
#include <algorithm>
#include <stack>
#include <map>

using namespace std;
#endif // !HEAD

#ifndef QUADMEMSET
inline void QuadMemSet(void* dst, int iSize, int value)
{
	iSize = iSize / 4;
	int* newDst = (int*)dst;
#ifdef WIN32
	__asm
	{
		mov edi, dst
			mov ecx, iSize
			mov eax, value
			rep stosd
	}
#else
	for (int i = 0; i < iSize; i++)
	{
		newDst[i] = value;

	}
#endif
}
#endif

struct EDGE
{
	int from;
	int to;
	int cost;
	EDGE* next;
};

int Dij(int s, int to, vector<EDGE*> &head,int N)
{
	vector<int> visited;
	visited.resize(N, 0);
	vector<int> res;
	res.resize(N, 10000000);
	res[s] = 0;
	//int t = s;
	while (true)
	{
		int v = -1;
		for (int t = 0; t<N; t++)
		{
			if (visited[t] == 0 && (v == -1 || res[v] > res[t]))
			{
				v = t;
			}
		}
		if (v == -1 || res[v] >= 10000000)
		{
			break;
		}
		visited[v] = 1;
		for (EDGE* p = head[v]; p; p = p->next)
		{
			if (visited[p->to] == 0)
			{
				res[p->to] = min(res[p->to], res[v] + p->cost);
			}
		}
	}
	return res[to];
}
EDGE edges[20000];
int main()
{
	int is_prime[101];
	int ab_isprime[10000];
	memset(is_prime, 1, sizeof(is_prime));
	memset(ab_isprime, 1, sizeof(ab_isprime));
	is_prime[0] = is_prime[1] = 0;
	for (int i = 2; i * i < 10001;i++)
	{
		if (is_prime[i])
		{
			for (int j = 2 * i; j < 101;j += i)
			{
				is_prime[j] = 0;
			}
			for (int j = max(2, (1000 + i - 1) / i) * i; j < 10000; j += i)
			{
				ab_isprime[j] = 0;
			}
		}
	}
	vector<int> abPrimes;
	map<int, int> mapIndex;
	for (int i = 1000; i < 10000;i++)
	{
		if (ab_isprime[i])
		{
			abPrimes.push_back(i);
			mapIndex[i] = abPrimes.size() - 1;
		}
	}

	vector<EDGE*> head;
	head.resize(abPrimes.size(), NULL);
	int count = 0;
	for (int i = 0; i < abPrimes.size();i++)
	{
		for (int j = 0; j < abPrimes.size();j++)
		{
			int countofzero = 0;
			int div = 1;
			while (div <= 1000)
			{
				if ((abPrimes[i]/div) % 10 - abPrimes[j] / div % 10 == 0)
				{
					countofzero++;
				}
				div *= 10;
			}
			if (i == j)
			{
				continue;
			}
			if (countofzero == 3)
			{
				EDGE edge;
				edge.from = i;
				edge.to = j;
				edge.cost = 1;
				edge.next = head[i];
				EDGE invedge = edge;
				invedge.from = j;
				invedge.to = i;
				edges[count] = edge;;
				head[i] = &edges[count++];
				invedge.next = head[j];
				edges[count] = invedge;
				head[j] = &edges[count++];
			}
		}
	}
#ifdef _DEBUG
	freopen("d:\\in.txt", "r", stdin);
#endif
	int N;
	scanf("%d\n", &N);
	for (int i = 0; i < N;i++)
	{
		int a, b;
		scanf("%d %d\n", &a, &b);
		if (a == b)
		{
			printf("0\n");
		}
		else
		{
			printf("%d\n", Dij(mapIndex[a], mapIndex[b], head, abPrimes.size()));
		}
	}
	return 0;
}

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/u011363774/article/details/37832691

智能推荐

云+X案例展 | 传播类:九州云 SD-WAN 携手上海电信,助力政企客户网络重构换新颜...-程序员宅基地

文章浏览阅读861次。戳蓝字“CSDN云计算”关注我们哦!本案例由九州云投递并参与评选,CSDN云计算独家全网首发;更多关于【云+X 案例征集】的相关信息,点击阅读原文丨挖掘展现更多优秀案例,为不同行业领域带..._sd-wan云网络 应用案例

开源啦!基于RT-Thread的百度语音识别——录音功能的实现(三)-程序员宅基地

文章浏览阅读1.3k次,点赞2次,收藏7次。本期分享来自RT-Thread的社区小伙伴霹雳大乌龙,如果你也有文章愿意分享/希望获得官方的写作指导,可以发送文章/联系方式邮件至邮箱:[email protected]..._rtthread audio驱动 pipe

Twitter的用户推荐算法_twitter推荐-程序员宅基地

文章浏览阅读1w次。关于Twitter的用户推荐算法,Quora上的文章有一个说明。算法基本分4步:First and foremost, we looked at who your friends follow, who they talk to, who they RT as gauges of your interest.Then we applied either positive/negative_twitter推荐

sso saml_使用签名的SAML断言实现身份提供者发起的SSO-程序员宅基地

文章浏览阅读2.4k次。随着越来越多的机构和组织在线提供服务和协作,员工需要访问内部部署和基于云的应用程序来进行日常工作。 这就要求实现单一登录(SSO)基础结构,使用户可以登录一次即可访问所有授权的内部和外部资源及应用程序。 具有大量Salesforce用户群的组织可以利用其现有的SSO基础结构将其实施到Force.com平台,该平台支持由外部SSO身份提供商提供的联合身份管理。 Force.com平台支持SSO的..._缺少 saml 持有者断言提供者签名证书

[opencv][原创]关于opencv-python的cv2保存视频不支持H264格式问题探讨_cv2.videowriter 不支持h264-程序员宅基地

文章浏览阅读2.7k次,点赞9次,收藏17次。项目有个不合理要求,能够在chrome浏览器打开播放,但是cv2根本不支持H264,由于版权原因,官方不支持h264格式所以当你使用诸如XVID,MJPG等虽然不影响使用和正常播放,但是就是无法在浏览器里面直接打开观看。查遍全网资料,发现Can you support "H264" codec? · Issue #299 · opencv/opencv-python · GitHub这个全网精华,但是里面尝试了下都不行,因此我得出结论要解决这个问题,只有2条路可行。第一条:源码编译这种方法耗时费_cv2.videowriter 不支持h264

Android实现文本复制到剪切板功能(ClipboardManager)_android] copy history support - clipboard manager,-程序员宅基地

文章浏览阅读4.8k次,点赞2次,收藏4次。Android也有剪切板(ClipboardManager),可以复制一些有用的文本到剪贴板,以便用户可以粘贴的地方使用,下面是使用方法注意:导包的时候API 11之前: android.text.ClipboardManagerAPI 11之后: android.content.ClipboardManager复制代码 代码如下:/** * 实现文本复制功能 _android] copy history support - clipboard manager, paste v5.5剪贴板管理器(12.7 mb)

随便推点

[软件工具][原创]使用软件实现labelme批量json_to_dataset最简单方法_修改labelme_json_to_dataset转换的颜色-程序员宅基地

文章浏览阅读978次。lableme批量转换工具可以很轻松实现将labelme标注的json文件转化为5个文件,即img.png、label.png、info.yaml、labels_name.txt以及label_viz.png。其中软件不需要安装python环境也不需要安装labelme这个软件,因为软件已经剥离labelme核心代码,全部嵌入软件功能中。大家都知道labelme的labelme_json_to_dataset都是针对单个文件转化,但是细心读代码会发现这个对于批量转化有个问题就是不同json转化的同一个目标颜_修改labelme_json_to_dataset转换的颜色

[C#][转载]如何在Ubuntu 18.04上安装Mono Mono develop_mono-dev ubuntu-程序员宅基地

文章浏览阅读578次。如何在Ubuntu 18.04上安装MonoMono是一个基于ECMA / ISO标准开发和运行跨平台应用程序的平台。它是Microsoft .NET框架的免费开源实现。本教程介绍了如何在Ubuntu 18.04上安装Mono。先决条件这些说明假定您以root用户或具有sudo特权的用户身份登录。在Ubuntu上安装Mono在Ubuntu 18.04上安装Mono的最简单和建议的方法是从Mono的存储库中安装它。这是一个相对简单的过程,只需几分钟。 首先安装必要的软件包:._mono-dev ubuntu

最快60秒完成新冠病毒核酸对比 阿里云向社会免费开放基因计算服务_新冠蛋白质序列比对-程序员宅基地

文章浏览阅读1.4k次。全球疫情肆虐,各大科技公司都在竭尽全力抗击疫情。3月13日,阿里云对外宣布,将向医疗科研机构、疾控中心等一线病毒研究机构免费开放基因计算服务,可大幅提升宏基因组测序、疫苗研发相关的处理效率,最快只需60秒即可完成新冠病毒的核酸对比工作。实时荧光定量PCR(RT-PCR)和宏基因组测序(mNGS)是目前用于确诊新型冠状病毒感染的常见方法,PCR操作流程简单、成本低,但准确率较低,mNGS虽然操作..._新冠蛋白质序列比对

cmake 链接 纯C编写的 *.a 静态库_cmake 链接.a-程序员宅基地

文章浏览阅读3.7k次。#cmake 配置if(CMAKE_SIZEOF_VOID_P EQUAL 8) set(_lib_suffix 64)else() set(_lib_suffix 32)endif()include_directories(${CMAKE_SOURCE_DIR}/lib) find_library(XXX_LIB xxxx${_lib_suffix}.a ${C..._cmake 链接.a

沃丰科技全方位赋能智能化体验交流会武汉站:基于AI技术,助力企业数字化转型_施耐德胡慧-程序员宅基地

文章浏览阅读160次。2021年4月23日,由沃丰科技主办的“2021 沃丰科技全方位赋能智能化体验交流会”在武汉成功举行。现场座无虚席,有近百名观众参会,沃丰科技副总裁傅亮、施耐德电气质量与客户满意中心卓越运营部门经理胡慧、统信软件交付中心总监韩辉、沃丰科技产品总监方晓东、沃丰科技产品总监姚广、沃丰科技客户体验咨询专家赵庐山就如何全方位赋能企业智能化做了分享。交流会现场随着新时代新技术不断发展,越来越多的企业将数字化转型作为公司的重要战略方向,积极探索数智化赋能企业新发展的有效路径。沃丰科技多年深耕智能客户体验领域,在数_施耐德胡慧

【超详细讲解】linux安装anaconda和pytorch及常见报错_anaconda3-2021.11-linux-x86_64.sh: 516: syntax err-程序员宅基地

文章浏览阅读5.6k次,点赞12次,收藏22次。一.首先连接服务器在powershell,gitbash或者vscode的命令行中输入命令:ssh 用户名@服务器IP地址二.安装conda//获取安装包wget https://repo.continuum.io/archive/Anaconda3-5.0.1-Linux-x86_64.sh//安装anaconda base命令bash Anaconda3-5.0.1-Linux-x86_64.sh//添加环境变量echo 'export PATH="~/anacond._anaconda3-2021.11-linux-x86_64.sh: 516: syntax error: "(" unexpected (expect

推荐文章

热门文章

相关标签