题目背景

本题不保证存在可以通过满足本题数据范围的任意数据做法。由于测试数据过水，可以通过此题的程序不一定完全正确（算法时间复杂度错误、或不保证正确性）。本题题目和数据仅供参考。本题不接受添加 hack 数据。

本题为错题。不建议尝试或提交本题。关于此类题目的详细内容

题目描述

有一位使者要游历各国，他每到一个国家，都能学到一种文化，但他不愿意学习任何一种文化超过一次（即如果他学习了某种文化，则他就不能到达其他有这种文化的国家）。不同的国家可能有相同的文化。不同文化的国家对其他文化的看法不同，有些文化会排斥外来文化（即如果他学习了某种文化，则他不能到达排斥这种文化的其他国家）。

现给定各个国家间的地理关系，各个国家的文化，每种文化对其他文化的看法，以及这位使者游历的起点和终点（在起点和终点也会学习当地的文化），国家间的道路距离，试求从起点到终点最少需走多少路。

输入格式

第一行为五个整数 N,K,M,S,T，每两个整数之间用一个空格隔开，依次代表国家个数（国家编号为1 到 N），文化种数（文化编号为 1 到 K），道路的条数，以及起点和终点的编号（保证 S 不等于 T）；

第二行为 N个整数，每两个整数之间用一个空格隔开，其中第 i个数 Ci​，表示国家 i的文化为 Ci​。

接下来的 K行，每行 K 个整数，每两个整数之间用一个空格隔开，记第i 行的第 j 个数为 aij​，aij​=1 表示文化 i 排斥外来文化j（i 等于 j 时表示排斥相同文化的外来人），aij​=0 表示不排斥（注意 i 排斥 j 并不保证 j 一定也排斥 i）。

接下来的 M 行，每行三个整数 u,v,d，每两个整数之间用一个空格隔开，表示国家 u与国家 v有一条距离为d的可双向通行的道路（保证u不等于 v，两个国家之间可能有多条道路）。

输出格式

一个整数，表示使者从起点国家到达终点国家最少需要走的距离数（如果无解则输出−1）。

输入输出样例

输入 #1复制

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

输出 #1复制

-1

输入 #2复制

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

输出 #2复制

10

说明/提示

输入输出样例说明1

由于到国家 2 必须要经过国家1，而国家2的文明却排斥国家 1 的文明，所以不可能到达国家 2。

输入输出样例说明2

路线为1 ->2

【数据范围】

对于 100%的数据，有2≤N≤100

1≤K≤100

1≤M≤N2

1≤ki​≤K

1≤u,v≤N

1≤d≤1000,S=T,1≤S,T≤N

NOIP 2012 普及组 第四题

代码实现：

#include <set>
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const size_t MAX_COUNTRIES(105);
const size_t MAX_ROADS(20050);

size_t countryCount;      // 国家数量
size_t cultureCount;      // 文化数量
unsigned int roadCount;   // 道路数量
size_t edgeCount;         // 边计数器
size_t startCountry;      // 起点国家
size_t endCountry;        // 终点国家

unsigned int roadStart;   // 道路起点
unsigned int roadEnd;     // 道路终点
unsigned int roadDistance;// 道路距离

unsigned int adjacencyHead[MAX_COUNTRIES];  // 邻接表表头
unsigned int edgeTarget[MAX_ROADS];         // 边的目标国家
unsigned int edgeWeight[MAX_ROADS];         // 边的权重（距离）
unsigned int nextEdge[MAX_ROADS];           // 下一条边

unsigned int countryCulture[MAX_COUNTRIES]; // 每个国家的文化
bool cultureExclude[MAX_COUNTRIES][MAX_COUNTRIES]; // 文化排斥关系

unsigned int shortestDist[MAX_COUNTRIES];   // 最短距离数组
bool inQueue[MAX_COUNTRIES];                // 是否在队列中

// 使用SPFA算法计算最短路径（预处理）
void calculateShortestPaths() {
    memset(shortestDist, 0X7F, sizeof(shortestDist));
    queue<unsigned int> nodeQueue;
    nodeQueue.push(startCountry);
    inQueue[startCountry] = true;
    shortestDist[startCountry] = 0;
    
    unsigned int currentNode;
    while (!nodeQueue.empty()) {
        currentNode = nodeQueue.front();
        nodeQueue.pop();
        inQueue[currentNode] = false;
        
        for (size_t edgeIndex = adjacencyHead[currentNode]; edgeIndex; edgeIndex = nextEdge[edgeIndex])
            if (shortestDist[edgeTarget[edgeIndex]] > shortestDist[currentNode] + edgeWeight[edgeIndex]) {
                shortestDist[edgeTarget[edgeIndex]] = shortestDist[currentNode] + edgeWeight[edgeIndex];
                if (!inQueue[edgeTarget[edgeIndex]]) {
                    inQueue[edgeTarget[edgeIndex]] = true;
                    nodeQueue.push(edgeTarget[edgeIndex]);
                }
            }
    }
}

unsigned int minDistance = 0X7F7F7F7FU;     // 最小距离结果
bool visitedCountry[MAX_COUNTRIES];         // 已访问的国家
set<unsigned int> learnedCultures;          // 已学习的文化集合

// 检查是否可以学习新文化（不会被已有文化排斥）
bool canLearnCulture(const unsigned int& cultureId) {
    for (set<unsigned int>::const_iterator it = learnedCultures.begin(); 
         it != learnedCultures.end(); ++it)
        if (cultureExclude[*it][cultureId])
            return false;
    return true;
}

// 使用DFS回溯寻找满足条件的最短路径
void findValidPath(const size_t& currentCountry, const unsigned int& currentDist) {
    visitedCountry[currentCountry] = true;
    learnedCultures.insert(countryCulture[currentCountry]);
    
    if (currentCountry == endCountry) {
        minDistance = min(minDistance, currentDist);
        return;
    }
    
    // 剪枝：如果当前距离加上预估最短距离已超过当前最优解
    if (currentDist + shortestDist[currentCountry] > minDistance) {
        visitedCountry[currentCountry] = false;
        learnedCultures.erase(countryCulture[currentCountry]);
        return;
    }
    
    for (size_t edgeIndex = adjacencyHead[currentCountry]; edgeIndex; edgeIndex = nextEdge[edgeIndex])
        if (!visitedCountry[edgeTarget[edgeIndex]] && canLearnCulture(countryCulture[edgeTarget[edgeIndex]]))
            findValidPath(edgeTarget[edgeIndex], currentDist + edgeWeight[edgeIndex]);
    
    visitedCountry[currentCountry] = false;
    learnedCultures.erase(countryCulture[currentCountry]);
}

int main() {
    // 读取输入
    scanf("%u%u%u%u%u", &countryCount, &cultureCount, &roadCount, &startCountry, &endCountry);
    
    // 读取每个国家的文化
    for (size_t i = 1; i <= countryCount; ++i)
        scanf("%u", countryCulture + i);
    
    // 读取文化排斥关系
    for (size_t i = 1; i <= cultureCount; ++i)
        for (size_t j = 1; j <= cultureCount; ++j)
            scanf("%d", &cultureExclude[i][j]);
    
    // 构建邻接表
    while (roadCount--) {
        scanf("%u%u%u", &roadStart, &roadEnd, &roadDistance);
        
        // 添加双向边
        ++edgeCount;
        edgeTarget[edgeCount] = roadEnd;
        edgeWeight[edgeCount] = roadDistance;
        nextEdge[edgeCount] = adjacencyHead[roadStart];
        adjacencyHead[roadStart] = edgeCount;
        
        ++edgeCount;
        edgeTarget[edgeCount] = roadStart;
        edgeWeight[edgeCount] = roadDistance;
        nextEdge[edgeCount] = adjacencyHead[roadEnd];
        adjacencyHead[roadEnd] = edgeCount;
    }
    
    // 预处理最短路径
    calculateShortestPaths();
    
    // 如果终点不可达，直接输出-1
    if (shortestDist[endCountry] == 0X7F7F7F7FU) {
        printf("-1");
        return 0;
    }
    
    // 使用DFS寻找满足条件的路径
    findValidPath(startCountry, 0);
    
    // 输出结果
    if (minDistance == 0X7F7F7F7FU)
        printf("-1");
    else
        printf("%u", minDistance);
    
    return 0;
}