====== 자취방 정하기 ======

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

===== 코드 =====
<dkpr py>
"""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()

</dkpr>
  * Dependency: 
    * [[:ps:teflib:graph#dijkstra|teflib.graph.dijkstra]]
    * [[:ps:teflib:search#bfs_iter|teflib.search.bfs_iter]]

{{tag>BOJ ps:problems:boj:골드_2}}