2019.03.15) 백준 최단경로 특집 4편 - 1238, 1389, 11403(PyPy3)

슬슬 우선순위 큐랑 플로이드 워샬도 적절할때 마구 사용할 수 있게 되었다.

1238번

from heapq import heappush, heappop
 
INF = 1e9
 
N, M, X = map(int, input().split(' '))
 
graph = {i: dict() for i in range(1, N + 1)}
 
for _ in range(M):
    a, b, c = map(int, input().split(' '))
    if graph[a].get(b, False):
        graph[a][b] = min(graph[a][b], c)
    else:
        graph[a][b] = c
 
 
# 우선순위 큐 구현
def search(start, end):
    hq = list()
    heappush(hq, (0, start))
    check = {i: INF for i in range(1, N + 1)}
 
    while hq:
        w, now = heappop(hq)
        if now == end:
            return check[end]
        if check[now] < w:
            continue
        for nxt in graph[now].keys():
            w2 = w + graph[now][nxt]
            if w2 < check[nxt]:
                check[nxt] = w2
                heappush(hq, (w2, nxt))
 
 
mx = 0
 
# i에서 X로 가는것, X에서 1에서 가는것이 왕복값
# 자신한테 가면 INF가 뜨므로 제외
for i in range(1, N + 1):
    if i == X:
        continue
    mx = max(search(i, X) + search(X, i), mx)
 
print(mx)
 

1389번

from heapq import heappush, heappop
 
INF = 1e9
 
N, M = map(int, input().split(' '))
 
graph = {i: list() for i in range(1, N + 1)}
 
for _ in range(M):
    a, b = map(int, input().split(' '))
    graph[a].append(b)
    graph[b].append(a)
 
 
# 우선순위 큐 구현
def search(start):
    hq = list()
    check = {i: INF for i in range(1, N + 1)}
    heappush(hq, (0, start))
    while hq:
        w, now = heappop(hq)
        if check[now] < w:
            continue
        for nxt in graph[now]:
            w2 = w + 1
            if w2 < check[nxt]:
                check[nxt] = w2
                heappush(hq, (w2, nxt))
    c = 0
    for i in range(1, N + 1):
        if i == start:
            continue
        c += check[i]
    return c
 
 
# 1부터 끝까지 탐색
min_num = 1
min = search(1)
for i in range(2, N + 1):
    if min > search(i):
        min_num = i
        min = search(i)
 
print(min_num)
 

11403번

c = int(input())
 
graph = [list(map(int, input().split(' '))) for _ in range(c)]
 
# 플로이드 워셜 알고리즘이라 쓰고 3중 반복문이라 읽는다
for k in range(c):
    for i in range(c):
        for j in range(c):
            graph[i][j] = 1 if graph[i][j] == 1 or graph[i][k] == graph[k][j] == 1 else 0
 
for i in range(c):
    for j in range(c):
        print(graph[i][j], end=' ')
    print()