Background

This problem does not guarantee the existence of a solution that can pass any data within the given constraints. Due to weak test data, programs that pass this problem may not be entirely correct (due to incorrect time complexity or lack of guaranteed correctness). The problem and data are provided for reference only. Adding hack data is not accepted for this problem.

This problem is considered flawed. It is not recommended to attempt or submit solutions to this problem. Detailed content regarding such problems

Problem Description

A messenger travels across various countries, learning a culture in each country he visits. However, he does not wish to learn any culture more than once (i.e., if he has learned a certain culture, he cannot visit other countries with the same culture). Different countries may share the same culture. Different cultures have varying views on other cultures; some cultures reject foreign cultures (i.e., if he has learned a certain culture, he cannot visit other countries that reject this culture).

Given the geographical relationships between countries, the cultures of each country, the views of each culture on other cultures, the starting and ending points of the messenger's journey (where he also learns the local culture), and the distances of roads between countries, determine the minimum distance the messenger needs to travel from the starting point to the ending point.

Input Format

The first line contains five integers $N, K, M, S, T$, separated by spaces, representing the number of countries (country IDs range from $1$ to $N$), the number of cultures (culture IDs range from $1$ to $K$), the number of roads, and the IDs of the starting and ending points (guaranteed that $S$ is not equal to $T$).

The second line contains $N$ integers, separated by spaces, where the $i$-th number $C_i$ represents the culture of country $i$.

The next $K$ lines, each containing $K$ integers separated by spaces, describe the cultural views. The $j$-th number on the $i$-th line is $a_{ij}$, where $a_{ij} = 1$ indicates that culture $i$ rejects culture $j$ (including rejecting itself when $i$ equals $j$), and $a_{ij} = 0$ indicates no rejection (note that $i$ rejecting $j$ does not guarantee that $j$ also rejects $i$).

The next $M$ lines, each containing three integers $u, v, d$ separated by spaces, describe the roads between countries. Each line indicates a bidirectional road of distance $d$ between country $u$ and country $v$ (guaranteed that $u$ is not equal to $v$, and there may be multiple roads between two countries).

Output Format

An integer representing the minimum distance the messenger needs to travel from the starting country to the ending country. If there is no solution, output $-1$.

Sample Input and Output

Input Sample #1

2 2 1 1 2 
1 2 
0 1 
1 0 
1 2 10 

Output Sample #1

-1

Input Sample #2

2 2 1 1 2 
1 2 
0 1 
0 0 
1 2 10 

Output Sample #2

10

Notes

Explanation of Input and Output Samples

Sample 1:

Since reaching country $2$ must pass through country $1$, and country $2$'s culture rejects country $1$'s culture, it is impossible to reach country $2$.

Sample 2:

The route is from $1$ to $2$.

Data Range:

For 100% of the data, the following constraints apply:

• $2 \leq N \leq 100$
• $1 \leq K \leq 100$
• $1 \leq M \leq N^2$
• $1 \leq k_i \leq K$
• $1 \leq u, v \leq N$
• $1 \leq d \leq 1000, S \neq T, 1 \leq S, T \leq N$

NOIP 2012 Junior Group Problem 4

见题面 Input 部分

见题面 Output 部分