| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 2048 MB | 228 | 51 | 30 | 22.556% |
수열 $a$가 주어질 때, $a$에서 인접한 원소의 차가 모두 1ドル$이라면 이러한 수열을 계단 수열이라고 합니다. 예를 들어, $[4,5,6,5,6]$과 $[1,2,3,2,1]$은 계단 수열이지만, $[1,2,3,5,4]$나 $[5,4,1,3,2]$는 계단 수열이 아닙니다.
정점 $N$개, 양방향 간선 $M$개로 구성된 그래프가 주어집니다. 그래프의 각 간선에는 1ドル$ 이상 $M$ 이하의 정수가 하나씩 적혀있습니다.
이 그래프의 정점 $u$에서 하나 이상의 인접한 간선을 따라 이동하는 것을 반복하여 정점 $v$에 도착했을 때, 통과한 간선에 적힌 정수를 나열한 수열이 계단 수열이라면 이를 정점 $u$에서 정점 $v$로 이동하는 계단 보행이라고 합니다. 이때 하나의 정점 또는 간선을 여러 번 사용할 수 있고, 하나의 간선을 여러 번 통과했다면 적힌 정수를 나열할 때에도 간선을 통과할 때마다 적어야 합니다. 이러한 계단 보행이 주어질 때, 그 길이는 이동 중 간선을 통과한 총 횟수로 정의합니다.
이때, 어떠한 보행이 계단 보행이 되기 위해서는 하나 이상의 인접한 간선을 따라 이동해야 함에 유의해야 합니다. 다시 말해, 정점 $u$에서 간선을 따라 이동하지 않고 정점 $u$에 남는 것은 정점 $u$에서 정점 $u$로 이동하는 계단 보행이 아닙니다.
1ドル \le i \le N$인 각 정수 $i$에 대해, 그래프의 1ドル$번 정점에서 $i$번 정점으로 이동하는 계단 보행이 존재하는지 알고자 합니다. 각 정점에 대해 그러한 계단 보행이 존재하는지 판단하고, 존재한다면 그중 가장 짧은 것의 길이를 출력해 주세요.
첫 번째 줄에 정점의 개수 $N$과 양방향 간선의 개수 $M$이 공백으로 구분되어 주어집니다.
두 번째 줄부터 $M$개의 줄에 각각 간선이 잇는 두 정점 $u_i,ドル $v_i$와 간선에 적힌 숫자 $x_i$가 공백으로 구분되어 주어집니다.
주어진 그래프에는 하나의 정점을 양끝으로 가지는 간선이 있거나 어떤 두 정점을 연결하는 간선이 여러 개 있을 수 있습니다.
총 $N$개의 정수를 한 줄에 공백으로 구분하여 출력합니다. 각각의 값은 다음과 같습니다.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 11 | $N \le 1000,ドル $M \le 2000$ |
| 2 | 28 | 서로 다른 두 간선이 같은 $x_i$ 값을 가지지 않습니다. |
| 3 | 61 | 추가 제약 조건이 없습니다. |
9 9 1 2 5 2 3 4 3 4 5 4 5 6 3 5 5 2 6 5 3 7 4 4 8 5 5 9 3
7 1 2 3 3 7 6 5 -1
예제에서 주어진 그래프는 다음과 같습니다.
각 정점에 대해 1ドル$번 정점에서 해당 정점으로 이동하는 계단 보행은 다음과 같습니다.
이때 1ドル$번 정점에서 1ドル$번 정점으로 이동하는 가장 짧은 계단 보행의 길이가 0ドル$이 아님에 유의합니다.
Contest > 한국정보기술진흥원 > 제4회 청소년 IT경시대회 > 중등부 3번