帮助与SPOJ算法问题 [英] Help with algorithm problem from SPOJ

问题描述

我认为这将是一个有趣的问题：总理

I thought it would be a fun problem: Prime Path

不过......这对我来说很难。 我唯一​​的想法就是做一些与背包问题......，没有其他想法。 难道你跟踪我的好方法吗？ 这不是对任何挑战或大学的功课。我只是想学到一些东西。

But...It is hard for me. My only idea is "To do something with knapsack problem".. and no other ideas. Could You track me for good way? It's not for any challenge or University homework. I just want to learn something.

_

好，但首先，如何找到这个素数？我是否需要找到所有的4位数质数，将其添加到图表？

Ok, but firstly, how to find this prime numbers? Do i need to find all 4digit prime numbers, add it to graph?

现在我已经产生的所有素数。

For now i have generating all prime numbers.

http://pastebin.com/wbhRNRHQ

你能不能给我的样品code申报图建立在邻居列表？

Could You give me sample code to declare graph build on neighbour list?

推荐答案

似乎是一个简单的图表寻路的问题。

Seems like a straightforward graph path finding problem.

取所有4位的素数的顶点。连接两个带边缘，如果我们可以从一边到另一边。

Take all 4 digit primes as the vertices. Connect two with an edge, if we can go from one to the other.

现在提供两个，你需要找到它们之间的最短路径，在图中，我们刚刚形成。一个简单的BFS（广度优先搜索）应该做的。

Now given two, you need to find the shortest path between them, in the graph we just formed. A simple BFS (breadth-first-search) should do for that.

有关的编程竞赛与时间限制，你甚至可以硬code每一个可能的素数对路径和接近零运行时间！

For programming contests with time limits, you could even hardcode every possible prime pair path and get close to zero running time!

这篇关于帮助与SPOJ算法问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！