PAST3M
https://gyazo.com/03933bba41c9b05e4ac79210321a5771
PAST3M
Thoughts.
At first glance, TSP but with so many vertices, could a more efficient algorithm be used? Characteristic problem conditions
Constant edge cost
You can use the same vertex or edge over and over.
The sides are held back by 10^5.
Different. For example, when going around 4 vertices, if s is in the center of the Y, cost 5, if s is at the end of the path, cost 3
Is it a tree?
Maybe so...
Problem Condition Overlooked
Instead of going around N cities, they were going around K cities.
Traveling salesman problem to find the distance between each of the K vertices first?
think again
K is as high as 16
16! cannot be searched in its entirety.
If it's a product of 2^16 cities already visited and 16 cities last visited, it's fine.
Vertex is 10^5
The sides are held back by 10^5.
Find the one to all shortest distance from 16 vertices with Dijkstra
Traveling salesman problem based on distances between 16 vertices
Note that the pattern does not return to the start
AC
code:python
def solve(N, M, edges, S, K, TS):
cc = CoordinateCompression(TS)
v2i, _i2v = cc.compress()
# dijkstra
from collections import defaultdict
distances = defaultdict(dict)
ds = one_to_all(S, N, edges)
from_start = {}
for t in TS:
for t in TS:
ds = one_to_all(t, N, edges)
for t2 in TS:
distances[v2it][v2it2] = dst2 # tsp
num_vertex = K
SUBSETS = 2 ** num_vertex
INF = 9223372036854775807
memo = [INF * num_vertex for _s in range(SUBSETS)] for subset in range(1, SUBSETS):
for v in range(num_vertex): # new vertex
mask = 1 << v
if subset == 1 << v:
# previous vertex is start
elif subset & mask: # new subset includes v
for u in range(num_vertex):
---
This page is auto-translated from /nishio/PAST3M. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I'm very happy to spread my thought to non-Japanese readers.