최단 경로 아니면 음수 사이클

$N$개의 정점과 $M$개의 간선을 가진 그래프가 주어진다. 정점은 $0, 1, \ldots, N-1$의 번호로 구분된다. 정점 $s$도 주어진다. 모든 정점 $0 \le i \le N-1$에 대해 $s$에서 $i$로 가는 경로가 존재한다.

$i$번 간선은 $a_i$번 정점에서 $b_i$번 정점으로 향하며, 정수 $c_i$의 가중치를 가진다. $c_i$는 음수일 수 있다.

그래프에 음수 사이클이 있으면, 그중 아무거나 하나를 반환하라.

음수 사이클이 없다면, 모든 정점 $0 \le t \le N-1$에 대해 $s$에서 $t$로 가는 최단 경로의 길이를 출력하라.

첫 번째 줄에 정수 $N$, $M$, $s$가 주어진다.

이후 $M$개의 줄에 각각 $a_i$, $b_i$, $c_i$가 주어진다.

그래프에 음수 사이클이 있는 경우:

• 첫 번째 줄에 CYCLE을 출력하라.
• 두 번째 줄에 음수 사이클의 간선 수 $k$를 출력하라. $k \ge 1$이다.
• 세 번째 줄에 $k+1$개의 정수 $u_0, u_1, \ldots, u_k$를 출력하라. $u_i$와 $u_{i+1}$은 사이클의 $i$번째 간선의 시작 정점과 끝 정점이다. $u_0 = u_k$이며, 사이클은 각 간선을 최대 한 번만 포함한다.

그래프에 음수 사이클이 없는 경우:

• 첫 번째 줄에 PATH를 출력하라.
• 두 번째 줄에 $N$개의 정수 $dist_0, dist_1, \ldots, dist_{N-1}$을 출력하라. $dist_i$는 $s$에서 $i$로 가는 최단 경로의 가중치 합이다.

• $2 \le N \le 20\,000$
• $1 \le M \le 20\,000$
• $0 \le s < N$
• $0 \le a_i, b_i \le N$
• $(a_i, b_i) \neq (a_j, b_j)$ ($i \neq j$)
• $-10^4 \le c_i \le 10^4$
• 모든 정점 $0 \le i \le N-1$에 대해 $s$에서 $i$로 가는 경로가 존재한다.