Description

A messenger plans to travel among countries. Each time he enters a country, he learns that country's culture. He refuses to learn any culture more than once; that is, once he has learned a culture, he cannot visit any other country that has the same culture. Different countries may share the same culture. Different cultures view other cultures differently: some cultures reject certain foreign cultures. Specifically, if he has learned a culture, then he cannot enter any country whose local culture rejects that learned culture. He also learns the local culture at both the start and the end.

Given the geography (countries and roads), each country's culture, each culture's view of other cultures, the start and end countries, and road distances, find the minimum total distance from the start to the end.

Input Format

The first line contains five integers $N, K, M, S, T$ separated by single spaces, denoting the number of countries (indexed $1$ to $N$), the number of cultures (indexed $1$ to $K$), the number of roads, and the indices of the start and the end, respectively. It is guaranteed that $S \ne T$.

The second line contains $N$ integers. The $i$-th integer $C_i$ denotes the culture of country $i$.

The next $K$ lines each contain $K$ integers separated by single spaces. Let the $j$-th integer on the $i$-th line be $a_{ij}$. If $a_{ij} = 1$, then culture $i$ rejects visitors who have learned culture $j$ (when $i = j$, it means rejecting visitors of the same culture). If $a_{ij} = 0$, it does not reject. Note that $i$ rejecting $j$ does not imply $j$ rejects $i$.

The next $M$ lines each contain three integers $u, v, d$ separated by single spaces, indicating an undirected road between countries $u$ and $v$ with distance $d$. It is guaranteed that $u \ne v$, and there may be multiple roads between the same pair of countries.

Output Format

Output a single integer: the minimum total distance for the messenger to travel from $S$ to $T$. If it is impossible, output $-1$.

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

-1

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

10

Hint

Explanation for Sample 1: Since reaching country $2$ must pass through country $1$, and the culture of country $2$ rejects the culture of country $1$, it is impossible to reach country $2$.

Explanation for Sample 2: The route is $1 \to 2$.

Constraints:

• For $100\%$ of the testdata:
  • $2 \le N \le 100$.
  • $1 \le K \le 100$.
  • $1 \le M \le N^2$.
  • $1 \le C_i \le K$.
  • $1 \le u, v \le N$.
  • $1 \le d \le 1000$.
  • $1 \le S, T \le N$.
  • $S \ne T$.

This is NOIP 2012 Junior Problem 4.

Translated by ChatGPT 5