Zigzag
2009.08.08 14:39 ACM/ICPC 2008
解説の通り Dijkstra で解いてみました。 与えられた点を通る2つの直線の組み合わせについて、交点を求め, その交点と入力された点の集合について TSP を解くような感じです。 状態は S[現在の点(入力された点のみ)][前にいた点][通った点の状態(入力された点のみ)] になります。
ただし、無駄な交点を作ってしまうとTLEになります。
コードは, Dijkstra の部分のみです。
| コメント(0) | トラックバック(0) | ↑ページトップ |