P1078 [NOIP 2012 Junior] Cultural Journey (suspected incorrect problem)

本题**不保证**存在**可以通过满足本题数据范围的任意数据**做法。由于测试数据过水，可以通过此题的程序不一定完全正确（算法时间复杂度错误、或不保证正确性）。本题题目和数据仅供参考。本题不接受添加 hack 数据。 本题为错题。**不建议尝试或提交本题。**[关于此类题目的详细内容](https://www.luogu.com.cn/paste/pf94n89x)

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.

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 a single integer: the minimum total distance for the messenger to travel from $S$ to $T$. If it is impossible, output $-1$.

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