โœ๏ธ ์ฝ”ํ…Œ ์ค€๋น„/Shortest Path

โœ๏ธ ์ฝ”ํ…Œ ์ค€๋น„/Shortest Path

[์ตœ๋‹จ ๊ฒฝ๋กœ] [Python] 10217. KCM Travel - GOLD โ… 

๋ณธ ๊ฒŒ์‹œ๊ธ€์€ PC๋ฒ„์ „์— ์ตœ์ ํ™” ๋˜์–ด์žˆ์Šต๋‹ˆ๋‹ค. 10217๋ฒˆ: KCM Travel ๊ฐ๊ณ ์˜ ๋…ธ๋ ฅ ๋์— ์ฐฌ๋ฏผ์ด๋Š” 2014 Google Code Jam World Finals์— ์ง„์ถœํ•˜๊ฒŒ ๋˜์—ˆ๋‹ค. ๊ตฌ๊ธ€์—์„œ ์˜จ ์ดˆ๋Œ€์žฅ์„ ๋ฐ›๊ณ  ๊ธฐ๋ปํ–ˆ๋˜ ๊ฒƒ๋„ ์ž ์‹œ, ์ฐฌ์ฐฌํžˆ ์ฝ์–ด๋ณด๋˜ ์ฐฌ๋ฏผ์ด๋Š” ์ค‘์š”ํ•œ ์‚ฌ์‹ค์„ ์•Œ์•„์ฐจ๋ ธ๋‹ค. ์ตœ๊ทผ์˜ ๋Œ€์„ธ www.acmicpc.net ์ž…๋ ฅ ์ž…๋ ฅ ํŒŒ์ผ์˜ ์ฒซ ๋ฒˆ์งธ ์ค„์— ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค์˜ ์ˆ˜๋ฅผ ์˜๋ฏธํ•˜๋Š” ์ž์—ฐ์ˆ˜ T๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๊ทธ ๋‹ค์Œ์—๋Š” T๊ฐœ์˜ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๊ฐ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค์˜ ์ฒซ ์ค„์—๋Š” ๊ณตํ•ญ์˜ ์ˆ˜ N (2 ≤ N ≤ 100), ์ด ์ง€์›๋น„์šฉ M (0 ≤ M ≤ 10,000), ํ‹ฐ์ผ“์ •๋ณด์˜ ์ˆ˜ K (0 ≤ K ≤ 10,000)๊ฐ€ ๊ณต๋ฐฑ์œผ๋กœ ๊ตฌ๋ถ„๋˜์–ด ์ฃผ์–ด์ง„๋‹ค. ์ด์–ด์„œ K๊ฐœ์˜ ์ค„์— ๊ฑธ์ณ ๊ฐ ํ‹ฐ์ผ“์˜ ์ถœ๋ฐœ๊ณตํ•ญ u, ๋„์ฐฉ..

โœ๏ธ ์ฝ”ํ…Œ ์ค€๋น„/Shortest Path

[์ตœ๋‹จ ๊ฒฝ๋กœ] [Python / C++] 1956. ์šด๋™ - GOLD โ…ฃ

๋ณธ ๊ฒŒ์‹œ๊ธ€์€ PC๋ฒ„์ „์— ์ตœ์ ํ™” ๋˜์–ด์žˆ์Šต๋‹ˆ๋‹ค. 1956๋ฒˆ: ์šด๋™ ์ฒซ์งธ ์ค„์— V์™€ E๊ฐ€ ๋นˆ์นธ์„ ์‚ฌ์ด์— ๋‘๊ณ  ์ฃผ์–ด์ง„๋‹ค. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) ๋‹ค์Œ E๊ฐœ์˜ ์ค„์—๋Š” ๊ฐ๊ฐ ์„ธ ๊ฐœ์˜ ์ •์ˆ˜ a, b, c๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. a๋ฒˆ ๋งˆ์„์—์„œ b๋ฒˆ ๋งˆ์„๋กœ ๊ฐ€๋Š” ๊ฑฐ๋ฆฌ๊ฐ€ c์ธ ๋„๋กœ๊ฐ€ ์žˆ๋‹ค๋Š” ์˜ www.acmicpc.net ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— V์™€ E๊ฐ€ ๋นˆ์นธ์„ ์‚ฌ์ด์— ๋‘๊ณ  ์ฃผ์–ด์ง„๋‹ค. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) ๋‹ค์Œ E๊ฐœ์˜ ์ค„์—๋Š” ๊ฐ๊ฐ ์„ธ ๊ฐœ์˜ ์ •์ˆ˜ a, b, c๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. a๋ฒˆ ๋งˆ์„์—์„œ b๋ฒˆ ๋งˆ์„๋กœ ๊ฐ€๋Š” ๊ฑฐ๋ฆฌ๊ฐ€ c์ธ ๋„๋กœ๊ฐ€ ์žˆ๋‹ค๋Š” ์˜๋ฏธ์ด๋‹ค. (a → b์ž„์— ์ฃผ์˜) ๊ฑฐ๋ฆฌ๋Š” 10,000 ์ดํ•˜์˜ ์ž์—ฐ์ˆ˜์ด๋‹ค. (a, b) ์Œ์ด ๊ฐ™์€ ๋„๋กœ๊ฐ€ ์—ฌ๋Ÿฌ ๋ฒˆ ์ฃผ์–ด์ง€์ง€ ์•Š๋Š”๋‹ค. ์ถœ๋ ฅ ์ฒซ์งธ ์ค„์— ์ตœ์†Œ..

kodo_o
'โœ๏ธ ์ฝ”ํ…Œ ์ค€๋น„/Shortest Path' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๊ธ€ ๋ชฉ๋ก