자취방 정하기

• 가중치가 확률적으로 주어지는 점이 새로울수 있는데, 사실 매우 단순하다. a-b-c 의 루트로 이동하는데에 걸리는 시간의 기댓값은 a-b에 걸리는 시간의 기댓값과 b-c에 걸리는 시간의 기댓값의 합이다 (기댓값의 선형성). 이렇게 생각하면 모든 엣지들에 대해서 가중치의 기댓값을 각각 계산하고 그 기댓값들로 그래프를 만든 다음에 최단 거리를 찾는 것과 동일하다. 그래서 시간이 T이하이면 자취방에 포함시키면 끝.
• 무향 그래프이므로, 각 자취방에서 학교까지의 거리를 구하는 것은, 그냥 학교에서 각 자취방까지의 거리를 구하는것과 동일하다. 단일 출발지 최단 경로 (Single Source Shortest Path) 알고리즘을 적당히 쓰면 되는데.. 신경쓸부분은 음수 가중치의 처리이다. 가중치의 기댓값이 음수가 되는 엣지가 존재하므로, 원칙적으로는 벨만포드나 SPFA를 사용해야 할것 같지만, 이렇게 되면 시간복잡도가 O(VE)가 된다.
• 하지만 무향 그래프라는 점을 이용하면 문제를 좀더 단순하게 풀수 있다. 음수 엣지가 존재하기만 하면 그 자체로 사이클이 된다. 그래서 음수 엣지까지 도달 가능하면 모든 도달가능한 노드까지의 거리가 -inf가 되고, 도달가능한 음수엣지가 없다면 그냥 다익스트라 알고리즘으로 O(ElogV)에 계산하면 된다.
  • 좀더 자세한 설명은 가중치가 양수 또는 음수인 그래프 참고
• 구현할때에는 가중치를 (a_i + b_i)/2 로 계산하는 대신, 실수값을 피하기 위해서 그냥 (a_i + b_i)로 지정한 다음 마지막에 최종 거리가 T*2 이하인지를 확인하는 방식으로 처리했다

"""Solution code for "BOJ 25619. 자취방 정하기".

- Problem link: https://www.acmicpc.net/problem/25619
- Solution link: http://www.teferi.net/ps/problems/boj/25619

Tags: [Dijkstra]
"""

import sys
from teflib import graph as tgraph
from teflib import search

SOURCE = 0


def main():
    N, M = [int(x) for x in sys.stdin.readline().split()]
    wgraph = [{} for _ in range(N)]
    neg_nodes = set()
    for _ in range(M):
        u, v, a, b = [int(x) for x in sys.stdin.readline().split()]
        wgraph[u - 1][v - 1] = wgraph[v - 1][u - 1] = a + b
        if a + b < 0:
            neg_nodes.update((u - 1, v - 1))
    T = int(sys.stdin.readline())

    connected_nodes = set(search.bfs_iter(lambda u: wgraph[u].keys(), 0))
    if connected_nodes & neg_nodes:
        answer = connected_nodes
    else:
        target_dist = T * 2
        dists = tgraph.dijkstra(wgraph, SOURCE)
        answer = {u for u, dist_u in enumerate(dists) if dist_u <= target_dist}
    answer.discard(SOURCE)

    print(len(answer))
    print(*(u + 1 for u in sorted(answer)))


if __name__ == '__main__':
    main()

• Dependency:
  • teflib.graph.dijkstra
  • teflib.search.bfs_iter