Informatica Online Judge

  괄호그래프 [2274 / 08E2]

Time Limit(Test case) : 500 (ms)
Number of users who solved : 7   Total Tried : 6


The Champion of this Problem (C++) : gs15120 - 0ms / 2495byte
My Best Submission (C++) : N/A

[koistudy.net (unkonwn)]

Background

세빈이와 민제는 n개의 정점과 m개의 단방향 간선으로 이루어진 그래프 위에서 사이좋게 살고 있다. 이 그래프에는 특이한 점이 하나 있는데, 모든 간선들에 특정한 괄호 문자들이 많이 떨어져 있다는 것이다. 한 간선에 떨어져 있는 괄호 문자들의 종류는 모두 같다. 또한 괄호 문자들의 종류는 총 8가지로, (, ), [, ], {, }, < , > 중 하나이다.

오늘은 민제의 생일이지만, 세빈이는 아무것도 준비하지 못했다! 그래서 세빈이는 민제에게 가는 경로 상에 있는 간선들에서 괄호 문자를 하나씩 주운 뒤 이를 순서대로 연결하여 민제에게 선물로 주기로 하였다. 하지만 민제가 얼마나 변태인지 잘 아는 세빈이는 이렇게 만들어진 괄호 문쟈열이 "올바른 괄호 문자열"이 아닐 경우, 민제가 거품을 물고 쓰러지게 될 것을 확신하고 있다. 따라서 정점 s에 살고 있는 세빈이는 "올바른 괄호 문자열"을 만들면서 정점 t에 살고 있는 민제에게 최대한 빠르게 가려고 한다.

어떠한 괄호 문자열 S가 올바른 괄호 문자열이라면, S는 다음 세 조건 중 하나를 만족한다 :
1. S는 길이가 0인 문자열이다.
2. 어떠한 올바른 괄호 문자열 X가 존재하여, S는 ( X )이거나, [ X ]이거나, { X }이거나, < X >이다.
3. 어떠한 올바른 괄호 문자열 X, Y가 존재하여, S는 XY이다.

세빈이가 다음 조건을 만족하며 행동해야 한다 :
1. 간선을 하나 지날 때마다 그 간선에 떨어져 있는 괄호 문자들 중 정확히 하나를 주워야 한다.
2. 같은 간선을 여러 번 지날 수 있지만, 그때마다 그 간선에 있는 괄호 문자를 다시 주워야 한다. 각 간선들에 떨어져 있는 괄호 문자의 수는 충분히 많다.
3. 괄호 문자열을 만들 때, 괄호 문자들을 주운 순서대로 연결해야 한다.

세빈이가 조건을 만족하면서 민제에게 가는 최단 경로의 길이를 출력하시오.

Input

첫째 줄에 네 정수 n, m, s, t가 주어진다.
둘째 줄부터 m + 1째 줄까지, (i + 1)번째 줄에는 두 정수 u_i, v_i와 문자 c_i가 주어지는데, 이는 정점 u_i에서 시작하여 v_i로 가는 간선에 괄호 문자 c_i들이 떨어져 있음을 의미한다.

모든 입력 데이터는 아래와 같은 조건을 만족한다 :
1 <= n <= 200
1 <= m <= 2000
1 <= s, t <= n
1 <= u_i, v_i <= n
c_i ∈ {(, ), [, ], {, }, < , >}

Output

만약 조건을 만족하는 경로가 존재하지 않는다면, 첫째 줄에 -1을 출력한다.
이외의 경우, 첫째 줄에 조건을 만족하는 최단 경로의 길이를 출력한다. 이 경우 최단 경로의 길이는 10^18 이하임이 보장된다.

IO Example

Sample Input 1

4 4 1 4
1 2 (
2 2 [
2 3 ]
3 4 )

Sample Output 1

4

Sample Input 2

5 4 1 5
1 2 <
2 3 {
3 4 >
4 5 }

Sample Output 2

-1

Note

예제 1에서, 최단 경로는 1 -> 2 -> 2 -> 3 -> 4이다. 이때 세빈이가 만든 괄호 문자열은 ([])이다.
예제 2에서, 정점 1에서 5로 가는 모든 경로는 조건을 만족하지 않는다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]