728x90
반응형

www.acmicpc.net/problem/1238

 

1238번: 파티

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어

www.acmicpc.net

import heapq
import sys
input = sys.stdin.readline 

n, m, x = map(int,input().split())
# n 명, 도로 m 개 , x 마을에서 

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

def dij(start):
  q = []
  heapq.heappush(q, (0,start))
  dist = [1e9]*(n+1)
  dist[start] = 0 

  while q:
    d, now = heapq.heappop(q)
    if dist[now]<d : continue 
    for i in graph[now]:
      cost = d + i[1]
      if cost < dist[i[0]]:
        dist[i[0]] = cost 
        heapq.heappush(q,(cost,i[0]))
  return dist 

result = [0]
dist_x = dij(x)
for i in range(1,n+1):
  result.append( dij(i)[x] + dist_x[i] ) 

print ( max(result) )
728x90
반응형

'백준 > 최단경로' 카테고리의 다른 글

# 18352 특정 거리의 도시 찾기  (0) 2021.04.10
# 1504 특정한 최단 경로  (0) 2021.04.10
# 1916 최소비용 구하기 파이썬  (0) 2021.04.09
# 1753 최단 경로 파이썬  (0) 2021.04.09
728x90
반응형

www.acmicpc.net/problem/18352

 

18352번: 특정 거리의 도시 찾기

첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개

www.acmicpc.net

import heapq
import sys
input = sys.stdin.readline 


n, m, k, x = map(int,input().split())
# 도시 도로 거리 출발 도시 
graph = [ [] for _ in range(n+1) ]
for i in range(m):
  a, b= map(int, input().split())
  graph[a].append(b)

# x에서 출발, 경로가 k 인 도시 오름차순 출력 없으면 -1 

def dij(start):
  q = []
  heapq.heappush(q, (0,start))
  dist = [1e9]*(n+1)
  dist[start]=0 

  while q:
    d, now = heapq.heappop(q)
    if dist[now]<d : continue 
    
    for i in graph[now]:
      cost = d + 1
      if cost<dist[i]:
        dist[i] = cost 
        heapq.heappush(q, (cost,i))
  return dist 

result = dij(x)
answer = []

for i in range(n+1) : 
  if result[i] == k : 
    answer.append(i)

if answer == [] : print(-1)
else:
  answer.sort()
  for i in answer: print(i)
728x90
반응형

'백준 > 최단경로' 카테고리의 다른 글

# 1238 파티  (0) 2021.04.10
# 1504 특정한 최단 경로  (0) 2021.04.10
# 1916 최소비용 구하기 파이썬  (0) 2021.04.09
# 1753 최단 경로 파이썬  (0) 2021.04.09
728x90
반응형

www.acmicpc.net/problem/1504

 

1504번: 특정한 최단 경로

첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존

www.acmicpc.net

import heapq
import sys
input = sys.stdin.readline

n, e = map(int,input().split()) # 정점, 간선 

graph=[ [] for _ in range(n+1) ]
for i in range(e): 
  a,b,c = map(int,input().split())
  graph[a].append((b,c))
  graph[b].append((a,c))

v1, v2 = map(int,input().split())

def dij(start):
  q = [] 
  heapq.heappush(q,(0,start))
  dist = [1e9]*(n+1)
  dist[start]=0 

  while q:
    d, now = heapq.heappop(q)
    if dist[now] < d : continue 

    for i in graph[now]:
      cost = d + i[1]
      if cost < dist[i[0]]:
        dist[i[0]] = cost 
        heapq.heappush(q, (cost,i[0]))
  return dist 


dist_1 = dij(1)
dist_v1 = dij(v1)
dist_v2 = dij(v2)

answer = min( dist_1[v1]+dist_v1[v2]+dist_v2[n], 
  dist_1[v2]+ dist_v2[v1]+dist_v1[n])

if answer >= 1e9 : 
  print(-1)
else : 
  print(answer)

 

주의사항 ) 

 

1. 양방향 그래프 => graph 에 추가할 때 앞 뒤로 다 해주기 

2. v1, v2 는 지나는 순서가 정해진 것은 x => 경우의 수 2개로 나누어서 더 작은 것으로 선택하기 

728x90
반응형

'백준 > 최단경로' 카테고리의 다른 글

# 1238 파티  (0) 2021.04.10
# 18352 특정 거리의 도시 찾기  (0) 2021.04.10
# 1916 최소비용 구하기 파이썬  (0) 2021.04.09
# 1753 최단 경로 파이썬  (0) 2021.04.09
728x90
반응형

www.acmicpc.net/problem/1916

 

1916번: 최소비용 구하기

첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그

www.acmicpc.net

import heapq
import sys
input = sys.stdin.readline 

n = int(input()) # 도시 
m = int(input()) # 버스 

graph = [ [] for _ in range(n+1)]
for i in range(m):
  s,e,c = map(int,input().split())
  graph[s].append((e,c)) # 도착, 비용 

s, e = map(int,input().split()) # 출발 도착 

def dij(start):
  q = []
  dist = [1e9]*(n+1)
  heapq.heappush(q, (0,start) )
  dist[start]=0

  while q : 
    d, now = heapq.heappop(q)

    if dist[now]< d : continue 

    for i in graph[now]:
      cost = d + i[1]
      if cost < dist[i[0]]:
        dist[i[0]] = cost 
        heapq.heappush(q, (cost,i[0]))

  return dist 

result = dij(s)
print(result[e])

 

기본 다익스트라 구현법 사용! 

728x90
반응형

'백준 > 최단경로' 카테고리의 다른 글

# 1238 파티  (0) 2021.04.10
# 18352 특정 거리의 도시 찾기  (0) 2021.04.10
# 1504 특정한 최단 경로  (0) 2021.04.10
# 1753 최단 경로 파이썬  (0) 2021.04.09
728x90
반응형

www.acmicpc.net/problem/1753

 

1753번: 최단경로

첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다.

www.acmicpc.net

import sys
import heapq 
input = sys.stdin.readline

V,e = map(int,input().split()) # 정점, 간선 
k = int(input()) # 시작 

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

for i in range(e):
  u,v,w = map(int,input().split())
  graph[u].append( (v,w) ) # 이어진 곳, 거리 

# 경로 존재하지 않으면 INF 

def dij(start):
  q = []
  dist = [1e9]*(V+1)
  heapq.heappush(q, (0,k) )
  dist[start]=0
  

  while q:
    d, now = heapq.heappop(q)

    if dist[now]< d : continue # 전에 방문한 적 있으면 처리하지 않음 

    for i in graph[now]:
      cost = d + i[1]
      if cost < dist[i[0]] :
        dist[i[0]] = cost
        heapq.heappush(q, (cost,i[0]))
  return dist 

result = dij(k)

for i in range(1,V+1):
  if result[i] == 1e9 : 
    print("INF")
  else:
    print(result[i])

 

 

정점 대문자 V 

중간에 입력 받는거 소문자 v.... 

728x90
반응형

'백준 > 최단경로' 카테고리의 다른 글

# 1238 파티  (0) 2021.04.10
# 18352 특정 거리의 도시 찾기  (0) 2021.04.10
# 1504 특정한 최단 경로  (0) 2021.04.10
# 1916 최소비용 구하기 파이썬  (0) 2021.04.09

+ Recent posts

티스토리툴바