32252번 - 가중치 복사 버그

문제

$N$개의 정점과 $M$개의 양방향 간선으로 이루어진 그래프가 있다. 정점에는 1ドル$부터 $N$까지 번호가 매겨져 있다. 각 간선에는 가중치가 있는데, 가중치는 0ドル$ 또는 1ドル$이다. 이제 정점 $s$에서 정점 $e$까지 가는 가능한 모든 경로의 길이 중 최솟값을 구하여라.

위 문제는 전형적인 ‘0-1 BFS’ 문제가 되므로 너무 쉽다. 하지만 아래와 같이 그래프에 가중치 복사 버그가 일어난다면 어떨까?

• 가중치가 $c$인 간선을 지나면, 그 직후 모든 간선의 가중치가 $c$만큼 증가한다.
• 여기서 가중치는 간선의 초기 가중치가 아니라 간선을 지나기 직전 시점의 가중치이다.

가중치 복사 버그를 고려하여, 정점 $s$에서 정점 $e$까지 가는 가능한 모든 경로의 길이 중 최솟값을 구하여라. 답은 이진수로 출력하며, 답이 0ドル$인 경우에는 0을 출력하고, 그렇지 않은 경우에는 0으로 시작하면 안 된다.

입력

첫째 줄에 정점의 수 $N$과 간선의 수 $M,ドル 시작 정점의 번호 $s$와 도착 정점의 번호 $e$가 공백을 사이에 두고 주어진다. (2ドル\le N\le 300,円 000$; 1ドル\le M\le 600,円 000$; 1ドル\le s,e\le N$; $s\ne e$)

이후 $M$개의 줄에 각 간선의 정보가 주어진다. 각 줄에는 $u,ドル $v,ドル $c$가 공백을 사이에 두고 주어진다. (1ドル\le u,v\le N$; $u\ne v$; $c\in\{0,1\}$) 이는 정점 $u$와 $v$를 연결하며 초기 가중치가 $c$인 간선이 있음을 의미한다.

$s$에서 $e$로 가는 경로가 적어도 하나 있다.

출력

정점 $s$에서 정점 $e$로 가는 가능한 모든 경로의 길이 중 최솟값을 출력한다.

답은 이진수로 출력하며, 답이 0ドル$인 경우에는 0을 출력하고, 그렇지 않은 경우에는 0으로 시작하면 안 된다.

제한

힌트