PAST3M

https://gyazo.com/03933bba41c9b05e4ac79210321a5771

PAST3M

Thoughts.

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:

# tsp

num_vertex = K

SUBSETS = 2 ** num_vertex

INF = 9223372036854775807

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):

---