12930번 - 두 가중치

N개의 정점으로 이루어진 그래프 G가 있다. 그래프의 정점은 0번부터 N-1번까지 번호가 매겨져 있다.

그래프 G의 모든 간선은 가중치를 2개 가지고 있고, 각각을 가중치 1, 가중치 2라고 한다.

0번 정점에서 1번 정점으로 가는 최단 경로를 찾는 프로그램을 작성하시오. 경로의 비용은 경로에 있는 간선의 가중치 1을 모두 더한 값인 W1과 가중치 2를 모두 더한 값인 W2를 곱해서 구할 수 있다.

첫째 줄에 정점의 수 N이 주어진다. (2 ≤ N ≤ 20)

둘째 줄부터 N개의 줄에는 그래프의 가중치 1에 대한 정보가, 그 다음 N개을 줄에는 가중치 2에 대한 정보가 주어진다.

i번 줄의 j번째 문자는 i에서 j로 가는 간선을 나타내며, 가중치는 1~9 또는 '.'이다. 가중치가 '.'인 경우에는 간선이 없는 것이다.

가중치 1의 정보를 weight1, 가중치 2의 정보를 weight2 라고 했을 때, 다음 조건을 만족한다.

• weight1[i][i] = weight2[i][i] = '.'
• weight1[i][j] = weight1[j][i]
• weight2[i][j] = weight2[j][i]
• weight1[i][j] == '.' 이면 weight2[i][j] == '.' 이며 그 역도 성립한다.

0번 정점에서 1번 정점으로 가는 최단 경로의 비용을 출력한다. 0번에서 1번으로 갈 수 없는 경우에는 -1을 출력한다.