[BOJ] 10159.์ ์ธ (Java)
๋๋ถ๋
10159๋ฒ: ์ ์ธ ์ฒซ ์ค์๋ ๋ฌผ๊ฑด์ ๊ฐ์ N ์ด ์ฃผ์ด์ง๊ณ , ๋์งธ ์ค์๋ ๋ฏธ๋ฆฌ ์ธก์ ๋ ๋ฌผ๊ฑด ์์ ๊ฐ์ M์ด ์ฃผ์ด์ง๋ค. ๋จ, 5 ≤ N ≤ 100 ์ด๊ณ , 0 ≤ M ≤ 2,000์ด๋ค. ๋ค์ M๊ฐ์ ์ค์ ๋ฏธ๋ฆฌ ์ธก์ ๋ ๋น๊ต ๊ฒฐ๊ณผ๊ฐ ํ ์ค์ ํ๋์ฉ www.acmicpc.net ์ด ๋ฌธ์ ์์๋ N๊ฐ์ ๋ฌผ๊ฑด, M ๊ฐ์ ๋ฌผ๊ฑด์์ด ์ฃผ์ด์ง๋ฉฐ, ๋ฌผ๊ฑด i์ ๋น๊ต ๊ฒฐ๊ณผ๋ฅผ ์ ์ ์๋ ๋ฌผ๊ฑด ์๋ฅผ ์ถ๋ ฅํ๋ ๋ฌธ์ ์
๋๋ค. ํด๋น ๋ฌธ์ ๋ฅผ ํ๊ธฐ ์ํด์๋ ํ๋ก์ด๋-์์
(Floyd-Warshall) ์๊ณ ๋ฆฌ์ฆ์ ์ ์ฉํด์ผ ํฉ๋๋ค. ํ๋ก์ด๋-์์
์ ๋ชจ๋ ์ ์ ์์ ๋ชจ๋ ์ ์ ์ผ๋ก์ ์ต๋จ ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ๋ ์๊ณ ๋ฆฌ์ฆ์ผ๋ก, ๊ฑฐ์ณ๊ฐ๋ ์ ์ ์ ๊ธฐ์ค์ผ๋ก ์๊ณ ๋ฆฌ์ฆ์ ์ํํฉ๋๋ค. ๊ทธ๋ฆฌ๊ณ ๋ฐ๋ณต๋ฌธ 3๊ฐ๊ฐ ์ค์ฒฉ๋์ด ์๋๋ฐ, ์ ์ผ ๋ฐ๊นฅ์ชฝ ๋ฐ๋ณต๋ฌธ์ ๊ฑฐ์ณ๊ฐ๋ ๊ผญ์ง์ , ๋ ๋ฒ์งธ ๋ฐ..