PAST3M

https://gyazo.com/03933bba41c9b05e4ac79210321a5771

PAST3M

考えたこと

特徴的な問題条件

辺のコストが一定

同じ頂点や辺を何度も使っていい

辺が10^5で抑えられてる

違う。例えば4つの頂点を回る時、Y字の中心にsがあったらコスト5、パスの端にsがあったら3

木であるか？

たぶんそうだと思うが…

問題条件見落とし

N個の街を巡るのではなくK個の街を巡るのだった

先にK個の各頂点間の距離を求めて巡回セールスマン問題？

改めて考える

Kは高々16

16!は全探索できない

既に訪問済みの都市2^16と、最後に訪問した都市16の積なら大丈夫

頂点は10^5

辺が10^5で抑えられてる

16個の頂点からのone to all最短距離をダイクストラで求める

16の頂点間の距離を元に巡回セールスマン問題

スタートに戻ってこないパターンなことに注意が必要

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