---

백준 5719 : 문제링크

• 문제유형 :

  • 그래프
  • 다익스트라 최단 경로 알고리즘

• 설명

  • 다익스트라 최단 경로에 포함되는 모든 간선을 추적한다
  • 최단 경로에 포함되는 모든 간선을 추적할 때 DFS를 사용하여 추적하여 제외시킨다
  • 제외된 간선 외에서 다익스트라 최단 경로 알고리즘으로 차선 최단 경로를 찾는다

• 풀이

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53

  from collections import deque import heapq import sys input = sys.stdin.readline def dijkstra(): heap_data = [] heapq.heappush(heap_data, (0, start)) distance[start] = 0 while heap_data: dist, now = heapq.heappop(heap_data) if distance[now] < dist: continue for i in adj[now]: cost = dist + i[1] if distance[i[0]] > cost and not dropped[now][i[0]]: distance[i[0]] = cost heapq.heappush(heap_data, (cost, i[0])) def bfs(): q = deque() q.append(end) while q: now = q.popleft() if now == start: continue for prev, cost in reverse_adj[now]: if distance[now] == distance[prev] + cost dropped[prev][now] = True q.append(prev) while True: n, m = map(int, input().split()) if n == 0: break start, end = map(int, input().split()) adj = [[] for _ in range(n + 1)] reverse_adj = [[] for _ in range(n + 1)] for _ in range(m): x, y, cost = map(int, input().split()) adj[x].append((y, cost)) reverse_adj[y].append((x, cost)) dropped = [[False] * (n + 1) for _ in range(n + 1)] distance = [1e9] * (n + 1) dijkstra() bfs() distance = [1e9] * (n + 1) dijkstra() if distance[end] != 1e9: print(distance[end]) else: print(-1)

Comment and share

---

백준 10282 : 문제링크

• 문제유형 :

  • 그래프
  • 다익스트라 최단 경로 알고리즘

• 설명

  • 정점의 개수 N, 간선의 개수 D
  • 우선순위 큐를 이용하여, 시간복잡도 O(NlogD)로 해결할 수 있습니다

• 풀이

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

  import heapq import sys input = sys.stdin.readline def dijkstra(strat): heap_data = [] heapq.heappush(heap_data, (0, start)) distance[start] = 0 while heap_data: dist, now = heapq.heappop(heap_data) if distance[now] < dist: continue for i in adj[now]: cost = dist + i[1] if distance[i[0]] > cost: distance[i[0]] = cost heapq.heappush(heap_data, (cost, i[0])) for _ in range(int(input())): n, m, start = map(int, input().split()) adj = [[] for i in range(n + 1)] distance = [1e9] * (n + 1) for _ in range(m): x, y, cost = map(int, input().split()) adj[y].append((x, cost)) dijkstra(start) count = 0 max_distance = 0 for i in distance: if i != 1e9: count += 1 if i > max_distance: max_distance = i print(count, max_distance)

Comment and share