```cpp
namespace Floyd // Ac
{
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
const int kMaxN = 100;
int n, k, m, s, t;
int dis[kMaxN + 5][kMaxN + 5];
int a[kMaxN + 5][kMaxN + 5], c[kMaxN + 5];
int read()
{
int res = 0;
char ch = getchar();
while (!isdigit(ch))
ch = getchar();
while (isdigit(ch))
{
res = res * 10 + ch - 48;
ch = getchar();
}
return res;
}
void init()
{
n = read(), k = read(), m = read(), s = read(), t = read();
for (int i = 1; i <= n; ++i)
c[i] = read();
if (c[s] == c[t])
exit((puts("-1"), 0));
for (int i = 1; i <= k; ++i)
for (int j = 1; j <= k; ++j)
a[i][j] = read();
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
dis[i][j] = (i ^ j ? 0x3f3f3f3f : 0);
for (int i = 1; i <= m; ++i)
{
int u = read(), v = read(), w = read();
dis[u][v] = dis[v][u] = w;
}
}
void floyd()
{
for (int k = 1; k <= n; ++k)
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
if (i ^ k and k ^ j and c[i] ^ c[k] and c[k] ^ c[j] and !a[c[i]][c[k]] and !a[c[j]][c[k]])
dis[i][j] = std::min(dis[i][j], dis[i][k] + dis[k][j]);
std::cout << (dis[s][t] ^ 0x3f3f3f3f ? dis[s][t] : -1) << std::endl;
}
int main()
{
init();
floyd();
return 0;
}
};
```
by Anguei @ 2018-06-26 13:12:56
@[yyfcpp](/space/show?uid=53062) 可能数据弱
by 越学越掂 @ 2018-06-26 13:17:16
@[yyfcpp](/space/show?uid=53062) 因为官方数据$aij$全是$0$
by tarjan @ 2018-06-26 13:18:33
@[tarjan](/space/show?uid=102098) 官方数据这么弱的吗。。
by Anguei @ 2018-06-26 13:27:06
@[yyfcpp](/space/show?uid=53062) 就是这样的，所以很多题解都是错的。
by tarjan @ 2018-06-26 13:28:43
太强大了%%%
by 404_notfound @ 2018-08-04 21:20:09