AOJ 1347: Shopping

なるほどなーという問題

問題はこちら

問題

ある商店街にN個の店が１列に並んでいる。店を回る順番についてm個の条件があり、c_i番目の店に行く前にd_i番目の店に先に行かなければならないとする。このとき、すべての店を回って出口まで行くのに必要な歩く距離の最小値を求めよ

解法

ある店間を通る回数を極力少なくしたい。入り口方向に戻る総距離を少なくすることを考える。よく考えてみるとc_i < d_iな区間については3回通れば済むことがわかる。したがってそのような区間を調べて、その区間では距離3を足していけばいい。

N, m = map(int, raw_input().split())
 
three = [False]*N
for loop in xrange(m):
    c, d = map(int, raw_input().split())
    if c < d:
        three[c:d] = [True]*len(three[c:d])
 
ans = 0
for i in xrange(N):
    ans += 1
    if three[i]:
        ans += 2
print ans+1