スポンサーサイト

--.--.-- --:--  スポンサー広告

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

| - | - | ↑ページトップ |




Zigzag

2009.08.08 14:39  ACM/ICPC 2008

ACM-ICPC 2008 Aizu, Problem J: Zigzag

解説の通り Dijkstra で解いてみました。 与えられた点を通る2つの直線の組み合わせについて、交点を求め, その交点と入力された点の集合について TSP を解くような感じです。 状態は S[現在の点(入力された点のみ)][前にいた点][通った点の状態(入力された点のみ)] になります。

ただし、無駄な交点を作ってしまうとTLEになります。

コードは, Dijkstra の部分のみです。


スポンサーサイト

テーマ : プログラミング - ジャンル : コンピュータ

| コメント(0) | トラックバック(0) | ↑ページトップ |

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。