SuperCon2006予選課題 part1

Powered by dKingyo CSS | TOEFL 突破 | Access | コンパイラ | HTML
http://algorithm-study.g.hatena.ne.jp/bbs/2
http://www.gsic.titech.ac.jp/supercon/supercon2006/yosen.html
より。

なるほど。

・・・・・・・・・・・・

・＊−−−−−−−−＊・

・−・・・・・・・・−・

・−・・・＊−−−−＊・

・−・・・−・・・・・・

・−・・・＊−−−−＊・

・−・・・・・・・・−・

・＊−−−−−−−−＊・

のはダメで。

・・・・・・・・・・・・

・＊−−−−・・−−＊・

・−・・・−・・−・−・

・−・・・＊−−−・＊・

・−・・・・・・・・−・

・−・・・＊−−−・＊・

・−・・・−・・−・−・

・＊−−−−・・−−＊・

はOKと･･･
いや、ちょっと直感で思いついただけだからこれ以上の答えがあるかもしれない･･･

とりあえず、戦略。

• 一つの頂点から二つしか線分が出ない
• どの経路から辿っても一番近くにある頂点を結んでいけば最短になる
• 一番近くにある頂点を探すのはｘとｙでソートしたニ分岐でもあれば検索は早くなるかも−

間違っているかもしれないけど＾＾；私の直感がこうしろとwhisperするのだ。

続く･･･