P3831 [SHOI2012] 回家的路

SHOI2012 D2T1

2046 年 OI 城的城市轨道交通建设终于全部竣工，由于前期规划周密，建成后的轨道交通网络由$2n$条地铁线路构成，组成了一个$n$纵$n$横的交通网。如下图所示，这$2n$条线路每条线路都包含$n$个车站，而每个车站都在一组纵横线路的交汇处。 出于建设成本的考虑，并非每个车站都能够进行站内换乘，能够进行站内换乘的地铁站共有$m$个，在下图中，标上方块标记的车站为换乘车站。已知地铁运行 1 站需要 2 分钟，而站内换乘需要步行 1 分钟。Serenade 想要知道，在不中途出站的前提下，他从学校回家最快需要多少时间（等车时间忽略不计）。 

无

无

对于 30%的数据，$n\le 50,m\le 1000$； 对于 60%的数据，$n\le 500,m\le 2000$； 对于 100%的数据，$n\le 20000,m\le 100000$；