최단거리

문제

그래프와 출발점, 도착점이 주어질 때 출발점에서 도착점까지 이동하기 위한 최단거리를 출력하는 프로그램을 작성하시오. 예를 들어, 아래 그림에서 출발 정점이 0, 도착 정점이 10이라고 할 때, 최단거리는 3이다.

 

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. ( 1 ≤ N ≤ 10,000, 1 ≤ M ≤ 1,000,000 ) 둘째 줄부터 간선의 정보가 주어진다. 각 줄은 두 개의 숫자 a, b로 이루어져 있으며, 이는 정점 a와 정점 b가 연결되어 있다는 의미이다. M+1 번째 줄에 대하여 출발점과 도착점의 정점 번호가 주어진다. 정점의 번호는 0번부터 N-1번까지이다.

 

출력

출발점에서 도착점까지 이동하기 위한 최단거리를 출력한다.

 

예제 입력

11 14

0 1

0 2

1 2

1 4

1 5

2 3

3 7

4 7

4 9

4 10

5 6

6 8

6 10

7 8

0 10

예제 출력

3

 

#코드(C스럽게...이렇게 짜면 시간초과)

import sys 
 
if __name__ == "__main__":
  n, m    = map(int, sys.stdin.readline().split())
  myGraph = [[] for i in range(n)]
  cost    = [[] for i in range(n)]
  cnt = 0
  for i in range(m):
    a, b = map(int, sys.stdin.readline().split())
    myGraph[a].append(b)
    myGraph[b].append(a)
    
    cost[a].append(1)
    cost[b].append(1)
    
  start, end = map(int, sys.stdin.readline().split())
  
  table = [0]*n
  check = [False]*n
  
  for i in range(n):
    table[i] = 987987987
  table[start] = 0
  
  for i in range(n):
    
    minValue, minIdx = 987987987, -1
    for j in range(n): # 0 ~ 10
      if check[j] == False and minValue > table[j]:
        minValue = table[j]
        minIdx   = j
    
    check[minIdx] = True
    
    for j in range(len(myGraph[minIdx])):
      node2 = myGraph[minIdx][j]
      cost2 = cost[minIdx][j]  
      
      if table[node2] > table[minIdx] + cost2: 
        table[node2] = table[minIdx] + cost2  
   
  print(table[end])

 

 

#코드(파이썬 스럽게)

from collections import defaultdict
import heapq
import sys
 
input=sys.stdin.readline
INF=int(1e9)
 
def dijkstra(graph,start,shortest):
  pq=[]
  heapq.heappush(pq,(0,start))
  
  while(pq):
    candShortest, now = heapq.heappop(pq)
    if(candShortest>shortest[now]): continue
  
    for adj in graph[now]:
      cost=candShortest+adj[1]
      if cost < shortest[adj[0]]:
        shortest[adj[0]]=cost
        heapq.heappush(pq,(cost,adj[0]))
 
 
if __name__=="__main__":
  n,m = map(int ,input().split())
  graph=defaultdict(list)
  for _ in range(m):
    v, adj = map(int,input().split())
    graph[v].append((adj,1))
    graph[adj].append((v,1))
    
  start,end=map(int,input().split())
  # for key,val in sorted(graph.items()):
  # print(key,val)
  shortest=[INF for _ in range(n)]
  dijkstra(graph, start, shortest)
  # print(shortest)
  print(shortest[end])