๋ฌธ์ ๋ณด๋ฌ๊ฐ๊ธฐ : www.acmicpc.net/problem/14938 14938๋ฒ: ์๊ฐ๊ทธ๋ผ์ด๋ ์์์ด๋ ์์ฆ ๊ฐ์ฅ ์ธ๊ธฐ๊ฐ ์๋ ๊ฒ์ ์๊ฐ๊ทธ๋ผ์ด๋๋ฅผ ์ฆ๊ธฐ๊ณ ์๋ค. ์๊ฐ๊ทธ๋ผ์ด๋๋ ์ฌ๋ฌ ์ง์ญ์ค ํ๋์ ์ง์ญ์ ๋ํ์ฐ์ ํ๊ณ ๋ํํ์ฌ, ๊ทธ ์ง์ญ์ ๋จ์ด์ ธ ์๋ ์์ดํ ๋ค์ ์ด์ฉํด ์๋ฐ์ด๋ฒ์ www.acmicpc.net ์ด๋ฒ ๋ฌธ์ ๋ ๋ค์ต์คํธ๋ผ(Dijkstra) ๋ฌธ์ ์์ต๋๋ค. ๋ค์ต์คํธ๋ผ ๊ธฐ๋ณธ ๋ฌธ์ ์์ ๊ฐ ์ง์ญ์ ์์ดํ ๊ฐ์๋ฅผ ๋ด์ ๋ฐฐ์ด๋ง ์ถ๊ฐํด์ฃผ๋ฉด ๋ฉ๋๋ค. ๐ ใ๋ฌธ์ ํ์ดใ 1. ๊ธธ์ ์๋ฐฉํฅ ํตํ์ด ๊ฐ๋ฅํ๋ฏ๋ก ๋ ์ง์ญ์ ์๋ฐฉํฅ์ผ๋ก ์ฐ๊ฒฐ 2. n๊ฐ์ ์ง์ญ ์ค ์ต๋ ๊ฐ๋ฅํ ์์ดํ ์ ์ต๋ ๊ฐ์๋ฅผ ๊ตฌํด์ผ ํ๋ฏ๋ก ๋ค์ต์คํธ๋ผ n๋ฒ ์ํ 3. ๋ํ ์ง์ญ์ ์ ์ธํ ๋ชจ๋ ์ง์ญ์ ๊ฑฐ๋ฆฌ๋ ๋ฌดํ๋๋ก ์ด๊ธฐํ (๋ํ ์ง์ญ์ 0) 4. ํ์ฌ๊น..