Tag: shortest path

def distance(x1, y1, x2, y2, r_squared):
    dist_sq = (x2 - x1) ** 2 + (y2 - y1) ** 2
    return dist_sq <= r_squared

def solve():

    N, R, D, X, Y = map(int, input().split())

    graph = [[0, 0]]
    for _ in range(N):
        graph.append(list(map(float, input().split())))

    v = [False] * (N + 1)
    
    q = deque([(X, Y, 0)])
    
    result = 0.0
    
    r_sq = R * R

    while q:
        cur_x, cur_y, count = q.popleft()

        for i in range(1, N + 1):
            target_x, target_y = graph[i]

            if not v[i] and distance(cur_x, cur_y, target_x, target_y, r_sq):
                v[i] = True

                result += (D / (2 ** count))
                
                q.append((target_x, target_y, count + 1))

    print(result)
solve()

from collections import defaultdict, deque

N, M = map(int, input().split())

taller = defaultdict(list)
shorter = defaultdict(list)

for _ in range(M):
    a, b = map(int, input().split())
    taller[a].append(b)
    shorter[b].append(a)

def bfs(graph, start):
    visited = set()
    q = deque([start])
    while q:
        node = q.popleft()
        for n in graph[node]:
            if n not in visited:
                visited.add(n)
                q.append(n)
    return visited

result = 0
for i in range(1, N+1):
    visited_taller = bfs(taller, i)
    visited_shorter = bfs(shorter, i)
    # 앞 뒤의 키를 모두 탐색 가능할 경우
    if len(visited_taller) + len(visited_shorter) == N - 1:
        result += 1

print(result)

from collections import defaultdict, deque

INF = float('inf')

def floyd(n, dist_list):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist_list[i][j] = min(dist_list[i][j], dist_list[i][k] + dist_list[k][j])

    min_sum = INF
    result = 0
    for i, sum_dist in enumerate(map(sum, dist_list), start=1):
        if min_sum > sum_dist:
            min_sum = sum_dist
            result = i

    return result

def main():
    N, M = map(int, input().split())

    dist_list = [[INF] * N for _ in range(N)]
    for i in range(0, N):
        dist_list[i][i] = 0

    for _ in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        dist_list[a][b] = 1
        dist_list[b][a] = 1
    
    print(floyd(N, dist_list))


if __name__ == "__main__":
    main()

INF = float("inf")


def floyd(n, dist_list):
    """플로이드 워셜"""

    for k in range(1, n + 1):
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                dist_list[i][j] = min(
                    dist_list[i][j], dist_list[i][k] + dist_list[k][j]
                )

    return dist_list


def print_result(dist_list):
    """결과 출력"""
    for dist in dist_list[1:]:
        for d in dist[1:]:
            print(d if d != INF else 0, end=" ")
        print()


def main():
    n = int(input())
    m = int(input())

    dist_list = [[INF] * (n + 1) for _ in range(n + 1)]

    for _ in range(m):
        a, b, c = map(int, input().split())
        dist_list[a][b] = min(dist_list[a][b], c)

    for i in range(1, n + 1):
        dist_list[i][i] = 0

    dist_list = floyd(n, dist_list)
    print_result(dist_list)


if __name__ == "__main__":
    main()

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

둘째 줄부터 M개의 줄에 걸쳐서 두 개의 자연수 A, B가 공백을 기준으로 구분되어 주어진다. 이는 A번 도시에서 B번 도시로 이동하는 단방향 도로가 존재한다는 의미다. (1 ≤ A, B ≤ N)

X로부터 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 K인 모든 도시의 번호를 한 줄에 하나씩 오름차순으로 출력한다.

이 때 도달할 수 있는 도시 중에서, 최단 거리가 K인 도시가 하나도 존재하지 않으면 -1을 출력한다.

단방향 그래프에서 특정 노드로부터의 최단 거리를 구하는 문제이다. 모든 간선의 가중치가 1이므로 BFS 또는 다익스트라로 해결할 수 있다.

import heapq
from collections import defaultdict

INF = float("inf")

N, M, K, X = map(int, input().split())

graph = defaultdict(list)

for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)


def dijkstra(start):
    dist_list = [INF] * (N + 1)
    dist_list[start] = 0
    q = [(0, start)]

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

        for n_node in graph[cur_node]:
            if dist + 1 < dist_list[n_node]:
                dist_list[n_node] = dist + 1
                heapq.heappush(q, (dist + 1, n_node))

    return dist_list


inf_cnt = 0
for node, dist in enumerate(dijkstra(X)[1:], start=1):
    if dist == K:
        print(node)
    else:
        inf_cnt += 1

if inf_cnt == N:
    print(-1)

N, K = map(int, input().split())
distance = [float('inf')] * 100001

def bfs_01(start):
    dq = deque([(0, start)])
    distance[start] = 0
    
    while dq:
        dist, c = dq.popleft()
        
        if distance[c] < dist:
            continue
            
        # 비용 0인 간선 (순간이동)
        n = c * 2
        if 0 <= n <= 100000 and dist < distance[n]:
            distance[n] = dist
            dq.appendleft((dist, n))  # 앞에 추가
        
        # 비용 1인 간선 (걷기)
        for n in (c + 1, c - 1):
            if 0 <= n <= 100000 and dist + 1 < distance[n]:
                distance[n] = dist + 1
                dq.append((dist + 1, n))  # 뒤에 추가

bfs_01(N)
print(distance[K])