自动搬运

查看原文

来自洛谷，原作者为

	Created_equal1 **

搬运于2025-08-24 21:20:41，当前版本为作者最后更新于2015-09-01 20:37:12，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

感觉许多题解都是依靠数据水才过的。。

我觉得正解应该是启发式搜索

首先跑一遍无视文化排斥的最短路。容易证明，无视文化排斥最短路的答案一定不大于考虑文化排斥的答案。

这样就可以用一个很强的剪枝了。

如果当前到的这个点的花费加上从这个点出发到终点的无视文化排斥的最短路的花费比答案还要大，那么就没有继续往下搜索的意义了——剪枝。

#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;
}