c – 在图表中查找至少访问一次X节点的最短电路

Given a non-directed,weighted (no negative values) graph with N nodes and E edges (a maximum of 1 edge between two nodes,an edge can only be placed between two different nodes) and a list of X nodes that you must visit,find the shortest path that starts from node 0,visits all X nodes and returns to node 0. There’s always at least one path connecting any two nodes.

Limits are 1 <= N <= 40 000 / 1 <= X <= 15 / 1 <= E <= 50 000

这是一个例子：

红色节点(0)应该是路径的开始和结束.您必须访问所有蓝色节点(1,2,3,4)并返回.这里最短的路径是：

0 -> 3 -> 4 -> 3 -> 2 -> 1 -> 0 with a total cost of 30

我想过使用Dijkstra找到所有X(蓝色)节点之间的最短路径,然后贪婪地选择最近的未访问的X(蓝色)节点,但它不起作用(在纸上提出32而不是30).我后来也注意到,只找到所有X节点对之间的最短路径将花费O(X * N ^ 2)时间,这个时间太大而节点数量太多.

我唯一可以找到的电路是Eulerian电路,它只允许访问每个节点一次(我不需要它).这可以用Dijkstra解决,还是有其他算法可以解决这个问题？