【正经题解】文化之旅

启发式搜索
首先跑一遍无视文化排斥的最短路。容易证明，无视文化排斥最短路的答案一定不大于考虑文化排斥的答案。
这样就可以用一个很强的剪枝了。
如果当前到的这个点的花费加上从这个点出发到终点的无视文化排斥的最短路的花费比答案还要大，那么就没有继续往下搜索的意义了——剪枝。

#include <set>
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const size_t Max_NK(105);
const size_t Max_M(20050);
size_t N;
size_t K;
unsigned int M;
size_t Total;
size_t S, T;
unsigned int u, v, d;
unsigned int Head[Max_NK];
unsigned int To[Max_M];
unsigned int Weight[Max_M];
unsigned int Next[Max_M];
unsigned int C[Max_NK];
bool A[Max_NK][Max_NK];//A[i][j]若为true表示i排斥j 
unsigned int Dist[Max_NK];
bool In_Q[Max_NK];
void Spfa()
{
    memset(Dist, 0X7F, sizeof(Dist));
    queue<unsigned int> Q;
    Q.push(S);
    In_Q[S] = true;
    Dist[S] = 0;
    unsigned int Top;
    while (Q.size())
    {
        Top = Q.front();
        Q.pop();
        In_Q[Top] = false;
        for (size_t i = Head[Top];i;i = Next[i])
            if (Dist[To[i]] > Dist[Top] + Weight[i])
            {
                Dist[To[i]] = Dist[Top] + Weight[i];
                if (!In_Q[To[i]])
                {
                    In_Q[To[i]] = true;
                    Q.push(To[i]);
                }
            }
    }
}
unsigned int Ans(0X7F7F7F7FU);
bool Went[Max_NK];
set<unsigned int> culture;
bool check(const unsigned int &cl)
{
    for (set<unsigned int>::const_iterator iter = culture.begin();
        iter != culture.end();++iter)
        if (A[*iter][cl])
            return false;
    return true;
}
void Dfs(const size_t &Now, const unsigned int &D)
{
    Went[Now] = true;
    culture.insert(C[Now]);
    if (Now == S)
    {
        Ans = min(Ans, D);
        return;
    }
    if (D + Dist[Now] > Ans)
        return;
    for (size_t i = Head[Now];i;i = Next[i])
        if (!Went[To[i]] && check(C[To[i]]))
            Dfs(To[i], D + Weight[i]);
    Went[Now] = false;
    culture.erase(C[Now]);
}
int main()
{
    scanf("%u%u%u%u%u", &N, &K, &M, &S, &T);
    for (size_t i = 1;i <= N;++i)
        scanf("%u", C + i);
    for (size_t i = 1;i <= K;++i)
        for (size_t j = 1;j <= K;++j)
            scanf("%d", &A[i][j]);
    while (M--)
    {
        scanf("%u%u%u", &u, &v, &d);
        ++Total;
        To[Total] = v;
        Weight[Total] = d;
        Next[Total] = Head[u];
        Head[u] = Total;
        ++Total;
        To[Total] = u;
        Weight[Total] = d;
        Next[Total] = Head[v];
        Head[v] = Total;
    }
    Spfa();
    if (Dist[T] == 0X7F7F7F7FU)
    {
        printf("-1");
        return 0;
    }
    Dfs(T, 0);
    if (Ans == 0X7F7F7F7FU)
        printf("-1");
    else
        printf("%u", Ans);
    return 0;
}