문제1368--경찰서 건설

1368: 경찰서 건설

실행시간 제한: 1 Sec  메모리사용 제한: 128 MB
제출: 293  통과: 82
[제출] [채점기록] [묻고답하기]

문제 설명

도시에 N 개의 지점이 있다. 이 지점들은 다른 지점들과 일방통행 도로로 연결될 수 있다.

시장인 당신은 이 지점들 중 일부에 경찰서를 건설하고자 한다. 각 지점마다 경찰서를 건설하는 비용이 다르며, i번째 지점에 경찰서를 건설하는 비용은Ci 이다.

경찰서의 관할 지역은, 경찰서가 위치한 지점으로부터 출발해 사건을 처리하고 돌아올 수 있는 모든 지점으로 정의된다. 모든 지점이 적어도 하나 이상의 경찰서의 관할 지역에 포함되도록 경찰서를 짓고자 할 때, 필요한 최소 비용은 얼마인가?

입력 설명

첫 행에는 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 행에는 지점의 수 N (1 <= N <= 50) 이 주어진다.

다음 행에는 각 지점에 경찰서를 건설할 때의 비용인 N 개의 정수 Ci 가 공백으로 구분되어 주어진다. 이 값들은 1 이상 10^6 이하이다.

다음 N 개의 행에 걸쳐서 각 지점들 사이의 연관 관계를 표현하는 길이가 N인 문자열이 각각 주어진다. i행 j열의 문자가 'Y'인 경우 지점 i에서 지점 j로 가는 일방통행 도로가 있음을 의미한다. i행 i열의 문자는 언제나 'N'이다. 

출력 설명

각 테스트 케이스에 대해 최소 비용을 한 행에 하나씩 순서대로 출력한다.

입력 예시 Copy

1
5
1 2 3 4 5
NNNYY
YNNNN
NNNYN
NNYNN
NYNNN

출력 예시 Copy

4

출처/분류