Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

最短経路

ARC 008 C - THE☆たこ焼き祭り2012

問題文 : THE☆たこやき祭り2012

AOJ 0275 - Railroad

問題文 : 鉄道路線

JOI春合宿 2008-day3 Nightman

問題文 : 夜警解法 :登場する点のうち,・警備員のいる点 ・建物の点を頂点としたグラフを作る. この際に, 建物の辺または対角線と交わっている時は辺を貼らないようにする.これが出来れば, あとはダイクストラ法を各点に行うだけである.コード : #include <cstdio> #</cstdio>…

JOI春合宿 2011-day4 orienteering

問題文 : オリエンテーリング解法 : 同じ高さの点が無いので, 前もって標高順で, チェックポイントについてトポロジカルソートを行う. その後は全点対の最短経路をO(N^2logN)程度で求め, dp[i][j] : 1人目がチェックポイントi, 2人目がチェックポイントj に…

IOI 2011-day2 Crocodile's Underground City

問題文 : ワニの地下都市(pdf注意)解法 : 出口につけばすぐに出ることが出来るので, 出口のノードのコストは0にしておく.そうでないすべてのノードについて, "出口までたどり着ける最短時間" "出口までたどり着ける2 番目の最短時間"を状態としてdijkstra を…

AOJ 2269 - Traveling Salesman Problem

問題 : 巡回セールスマン問題解法 : 与えられたグラフは,(validなものであれば) 問題の制約通り, 有向木に辺をいくつか(最大501本)足したものとなる. また, 枝分かれや併合・子がある(となる)頂点が, 述べ 1000 個程度より多くあると, validなグラフが構成で…

JOI春合宿 2007-day3 Route

問題文 : 象使い(pdf注意, 2-3ページ目)解法 : 辺と辺で成される角を求めるには, (直前の点, 今いる点, 次に行く点)の3つの情報が必要である.直前の点をvec(P_0) = (x0, y0), 今いる点をvec(P_1) = (x1, y1), 次に行く点をvec(P_2) = (x2, y2) とすると (vec…

AOJ 0224 - Bicycle Diet

問題文 : 自転車ダイエット解法 : ケーキ屋の数が少ないので, 訪れたケーキ屋の集合および今いる頂点を持ったダイクストラを行う. "一度訪れたケーキ屋に再び訪れることができない"ということに注意.コード : #include <cstdio> #include <cstring> #include <cstdlib> #include <algorithm> #incl</algorithm></cstdlib></cstring></cstdio>…