백준 온라인 저지, 최단경로 / 19584번: 난개발 (파이썬 / 백준 골드문제)

문제 이 사실은 대회에 참가하고 있는 여러분들만 알고 있는 사실이다. 방금 외계인들이 지구를 정복했고 서울시청과 서울시의회를 장악했다. 이들은 인간들이 통근과 통학으로 고통받게 하려고 대규모 토목공사를 기획하고 있는데, 바로 지상에 서울 지하철 10호선을 짓는 것이다. ‘10호선을 만들어 준다니 좋은 거 아닌가?’라고 생각할지도 모르겠지만, 이들의 목적은 따로 있다. 바로 도로들을 철도노선으로 전부 가로막아 버리는 것이다. 이렇게 되면 서울의 남북을 가로지르는 버스 노선은 전부 사라지게 된다. 좋은 소식은 여러분들이 이 계획을 알고 있다는 것이다. 외계인들은 뛰어난 건축 기술을 갖고 있지만 x축에 평행하도록 철길을 놓을 때 가장 빠르게 철길을 완성할 수 있으므로 그렇게 할 것이다. 철길의 시점과 종점은 ..

2021.09.15