25619번 - 자취방 정하기

새내기 현서는 이번 학기에도 고민이 많은데, 그중 가장 큰 고민은 아침 수업이 많아서 수업 시간에 맞춰 강의실을 도착하지 못할 것 같다는 것이다! 고민 끝에 현서는 학교 주변의 자취방을 하나 구하기로 결심했다.

학교 주변은 정점이 N개, 간선이 M개인 그래프로 표현된다. 학교는 1번 정점에 있으며, 그 외의 정점에는 현서가 계약할 수 있는 자취방이 하나씩 있다. 간선은 학교와 자취방, 또는 자취방과 자취방 사이의 도로를 나타낸다. 도로는 양쪽 방향으로 모두 사용할 수 있다.

각 도로는 교통량이라는 값을 가지며, 교통량이 x인 도로를 통과하는 데에는 양쪽 방향으로 동일하게 x분의 시간이 걸린다. 다양한 사건에 의해서 각 도로의 교통량은 매번 일정하지는 않는데, 구체적으로 i번 도로의 교통량은 절반의 확률로 a_i이고, 나머지 절반의 확률로 b_i가 된다. 교통량은 각 도로마다 독립적으로 정해지며, 현서가 길을 지날 때마다 바뀔 수 있다. a_i 또는 b_i가 음수일 수도 있는데, 이 경우에는 도로를 통과할 때 시간이 역행한다고 생각하면 된다.

이 상황에서 현서는, 적당한 정해진 이동을 선택했을 때 학교에 도착했을 때 걸리는 시간의 기댓값이 T분 이하가 되도록 할 수 있는 위치의 자취방을 고려하려고 한다. 구체적으로는 아래와 같다.

• 1번 정점을 제외한 모든 정점 i에 대해, W_i를 i번 정점에서 1번 정점으로의 모든 가능한 이동의 집합이라고 정의하자.
  • s에서 e로의 이동은 s에서 시작해서 연결된 간선들만을 따라 이동해 e에 도착하는 것이다.
  • 이동은 간선을 중복해서 사용하는 것도 허용하며, 도착 정점인 1번 정점에 도착했다고 해서 멈출 필요 역시 없다.
• 모든 2 ≤ i ≤ n에 대해 함수 f_i : W_i → ℝ을
  f_i(w) = (i번 정점에서 이동 w를 이용하여 1번 정점으로 갈 때 걸리는 분 단위 시간의 기댓값)
  으로 정의하자. 이때 ℝ은 실수 전체의 집합이다.
• 현서는 f_i(w) ≤ T인 w ∈ W_i가 존재하는 정점만을 고려하려고 한다.

현서를 위해 위 조건을 만족하는 자취방들을 모두 구해주자.

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N, M ≤ 200 000)

둘째 줄부터 M개의 줄에 걸쳐 각 간선이 잇는 두 정점의 번호 u_i와 v_i, 그리고 정수 a_i와 b_i가 공백으로 구분되어 주어진다. (1 ≤ u_i, v_i ≤ N; u_i ≠ v_i; −10⁹ ≤ a_i, b_i ≤ 10⁹) 같은 정점 쌍을 두 번 잇는 입력은 주어지지 않는다. 즉, 모든 1 ≤ i, j ≤ M에 대해 {u_i, v_i} = {u_j, v_j}이면 i = j이다.

(M + 2)째 줄에 정수 T가 주어진다. (−2 × 10¹⁵ ≤ T ≤ 2 × 10¹⁵)

첫째 줄에 조건을 만족하는 자취방의 개수 K를 출력한다. 조건을 만족하는 자취방이 없으면 0을 출력한다.

첫째 줄에 0이 아닌 값을 출력했다면, 둘째 줄에 조건을 만족하는 자취방들이 위치한 정점의 번호를 공백으로 구분하여 오름차순으로 출력한다.

첫 번째 예제에서, 2번 정점의 경우 2 → 3 → 1 순으로 이동하면 기댓값이 4분이 된다. 3번 정점의 경우 3 → 1 순으로 이동하면 기댓값이 2.5분이 된다.

세 번째 예제에서 주어지듯이, 학교에서 도달할 수 없는 자취방이 같이 주어지는 것도 가능하다.