๐ŸšŒ ์ตœ์†Œ๋น„์šฉ ๊ตฌํ•˜๊ธฐ 2

๋ฐฑ์ค€ Gold3

์ตœ์†Œ๋น„์šฉ ๊ตฌํ•˜๊ธฐ 2

๋ฌธ์ œ

n(1โ‰คnโ‰ค1,000)๊ฐœ์˜ ๋„์‹œ๊ฐ€ ์žˆ๋‹ค. ๊ทธ๋ฆฌ๊ณ  ํ•œ ๋„์‹œ์—์„œ ์ถœ๋ฐœํ•˜์—ฌ ๋‹ค๋ฅธ ๋„์‹œ์— ๋„์ฐฉํ•˜๋Š” m(1โ‰คmโ‰ค100,000)๊ฐœ์˜ ๋ฒ„์Šค๊ฐ€ ์žˆ๋‹ค. ์šฐ๋ฆฌ๋Š” A๋ฒˆ์งธ ๋„์‹œ์—์„œ B๋ฒˆ์งธ ๋„์‹œ๊นŒ์ง€ ๊ฐ€๋Š”๋ฐ ๋“œ๋Š” ๋ฒ„์Šค ๋น„์šฉ์„ ์ตœ์†Œํ™” ์‹œํ‚ค๋ ค๊ณ  ํ•œ๋‹ค. ๊ทธ๋Ÿฌ๋ฉด A๋ฒˆ์งธ ๋„์‹œ์—์„œ B๋ฒˆ์งธ ๋„์‹œ ๊นŒ์ง€ ๊ฐ€๋Š”๋ฐ ๋“œ๋Š” ์ตœ์†Œ๋น„์šฉ๊ณผ ๊ฒฝ๋กœ๋ฅผ ์ถœ๋ ฅํ•˜์—ฌ๋ผ. ํ•ญ์ƒ ์‹œ์ž‘์ ์—์„œ ๋„์ฐฉ์ ์œผ๋กœ์˜ ๊ฒฝ๋กœ๊ฐ€ ์กด์žฌํ•œ๋‹ค.

์ž…๋ ฅ

์ฒซ์งธ ์ค„์— ๋„์‹œ์˜ ๊ฐœ์ˆ˜ n(1โ‰คnโ‰ค1,000)์ด ์ฃผ์–ด์ง€๊ณ  ๋‘˜์งธ ์ค„์—๋Š” ๋ฒ„์Šค์˜ ๊ฐœ์ˆ˜ m(1โ‰คmโ‰ค100,000)์ด ์ฃผ์–ด์ง„๋‹ค. ๊ทธ๋ฆฌ๊ณ  ์…‹์งธ ์ค„๋ถ€ํ„ฐ m+2์ค„๊นŒ์ง€ ๋‹ค์Œ๊ณผ ๊ฐ™์€ ๋ฒ„์Šค์˜ ์ •๋ณด๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๋จผ์ € ์ฒ˜์Œ์—๋Š” ๊ทธ ๋ฒ„์Šค์˜ ์ถœ๋ฐœ ๋„์‹œ์˜ ๋ฒˆํ˜ธ๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๊ทธ๋ฆฌ๊ณ  ๊ทธ ๋‹ค์Œ์—๋Š” ๋„์ฐฉ์ง€์˜ ๋„์‹œ ๋ฒˆํ˜ธ๊ฐ€ ์ฃผ์–ด์ง€๊ณ  ๋˜ ๊ทธ ๋ฒ„์Šค ๋น„์šฉ์ด ์ฃผ์–ด์ง„๋‹ค. ๋ฒ„์Šค ๋น„์šฉ์€ 0๋ณด๋‹ค ํฌ๊ฑฐ๋‚˜ ๊ฐ™๊ณ , 100,000๋ณด๋‹ค ์ž‘์€ ์ •์ˆ˜์ด๋‹ค.

๊ทธ๋ฆฌ๊ณ  m+3์งธ ์ค„์—๋Š” ์šฐ๋ฆฌ๊ฐ€ ๊ตฌํ•˜๊ณ ์ž ํ•˜๋Š” ๊ตฌ๊ฐ„ ์ถœ๋ฐœ์ ์˜ ๋„์‹œ๋ฒˆํ˜ธ์™€ ๋„์ฐฉ์ ์˜ ๋„์‹œ๋ฒˆํ˜ธ๊ฐ€ ์ฃผ์–ด์ง„๋‹ค.

์ถœ๋ ฅ

์ฒซ์งธ ์ค„์— ์ถœ๋ฐœ ๋„์‹œ์—์„œ ๋„์ฐฉ ๋„์‹œ๊นŒ์ง€ ๊ฐ€๋Š”๋ฐ ๋“œ๋Š” ์ตœ์†Œ ๋น„์šฉ์„ ์ถœ๋ ฅํ•œ๋‹ค.

๋‘˜์งธ ์ค„์—๋Š” ๊ทธ๋Ÿฌํ•œ ์ตœ์†Œ ๋น„์šฉ์„ ๊ฐ–๋Š” ๊ฒฝ๋กœ์— ํฌํ•จ๋˜์–ด์žˆ๋Š” ๋„์‹œ์˜ ๊ฐœ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค. ์ถœ๋ฐœ ๋„์‹œ์™€ ๋„์ฐฉ ๋„์‹œ๋„ ํฌํ•จํ•œ๋‹ค.

์…‹์งธ ์ค„์—๋Š” ์ตœ์†Œ ๋น„์šฉ์„ ๊ฐ–๋Š” ๊ฒฝ๋กœ๋ฅผ ๋ฐฉ๋ฌธํ•˜๋Š” ๋„์‹œ ์ˆœ์„œ๋Œ€๋กœ ์ถœ๋ ฅํ•œ๋‹ค.

์˜ˆ์ œ ์ž…๋ ฅ 1

5
8
1 2 2
1 3 3
1 4 1
1 5 10
2 4 2
3 4 1
3 5 1
4 5 3
1 5

์˜ˆ์ œ ์ถœ๋ ฅ 1

4
3
1 3 5

๐Ÿ“– ์•Œ๊ณ ๋ฆฌ์ฆ˜

แ„‹แ…งแ†ซแ„‰แ…ณแ†ธแ„Œแ…กแ†ผ-6

์˜ˆ์ œ๋ฅผ ๊ทธ๋ฆผ์œผ๋กœ ํ‘œํ˜„ํ•ด๋ณด๋ฉด ์œ„์™€ ๊ฐ™๋‹ค.

๋ฒ„์Šค ๋น„์šฉ์ด ์กด์žฌํ•˜๋Š” ๋…ธ์„ ๋„์—์„œ A ๋„์‹œ์—์„œ B ๋„์‹œ๋กœ ๊ฐ€๋Š” ์ตœ์†Œ ๋น„์šฉ์„ ์ถœ๋ ฅํ•˜๋Š” ๋ฌธ์ œ์ด๋‹ค.

์ด๋ฅผ ์ผ๋ฐ˜ํ™” ํ•˜๋ฉด [Weight๊ฐ€ ์กด์žฌํ•˜๋Š” ๊ทธ๋ž˜ํ”„์—์„œ ํŠน์ • ๋…ธ๋“œ์—์„œ ํŠน์ • ๋…ธ๋“œ๋กœ ๊ฐ€๋Š” ์ตœ์†Œ ๋น„์šฉ์„ ๋ฌป๋Š”] ๋ฌธ์ œ๋กœ ๋ฐ”๋ผ๋ณผ ์ˆ˜ ์žˆ๋‹ค. ๋ฐ”๋กœ ๋‹ค์ต์ŠคํŠธ๋ผ๋ฅผ ๊ฐ–๋‹ค ์จ์ฃผ๋ฉด ๋œ๋‹ค.

๋‹ค์ต์ŠคํŠธ๋ผ ๊ธฐ๋ณธ ๋ฌธ์ œ์—์„œ ๊ฒฝ๋กœ๋ฅผ ์ €์žฅํ•˜์—ฌ ์ถœ๋ ฅํ•ด์ค€๋‹ค๋Š” ์กฐ๊ฑด๋งŒ ์ถ”๊ฐ€ํ•˜๋ฉด ๋œ๋‹ค.

๐Ÿ‘จ๐Ÿปโ€๐Ÿ’ป CODE

import heapq as h
import sys
input = sys.stdin.readline
INF = int(1e9)
city = int(input())
bus = int(input())

graph = [[] for _ in range(city+1)]

for i in range(bus):
    a,b,c = map(int,input().split())
    graph[a].append((b,c))

start,end = map(int,input().split())
####



def dijkstra(start):
    distance = [INF]*(city+1)
    heap = []
    h.heappush(heap,(0,start))
    distance[start] = 0
    path = [[] for _ in range(city+1)] # ๊ฒฝ๋กœ
    path[start].append(start)

    while heap:
        dist,now = h.heappop(heap)

        if distance[now] < dist:
            continue

        for i in graph[now]:
            cost = dist + i[1]

            if cost < distance[i[0]]:
                distance[i[0]] = cost
                h.heappush(heap,(cost,i[0]))
                path[i[0]] = []
                for j in path[now]:
                    path[i[0]].append(j)
                path[i[0]].append(i[0])
    
    return distance,path

distance,path = dijkstra(start)
print(distance[end])
print(len(path[end]))
print(" ".join(map(str,path[end])))

ยฉ 2022. All rights reserved.

Powered by Hydejack v9.1.6