P1078 [NOIP 2012 普及组] 文化之旅

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

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

下面是这道题的链接
https://www.luogu.com.cn/problem/P1078

说下这道题的总结：

这道题目其实（应该）没有想象中的难，一个DFS加简单的剪枝应该就能过。首先说一下剪枝。对于国家i、j间的多条路径，可以在输入时就直接取其中距离最短的路径，把其它路径直接扔掉。显然这种方法对于求最优解无影响，且得到的总距离也较小。接下来假设一条路径可经过国家i到达终点t（且该路径距离最短），很显然s到i的路径也是最短的，i到t的路径也是最短的，故建立一数组sum[i]来表示到达国家i的最短路径，当dfs到国家i时若此时的总距离>=sum[i]，则直接结束递归，这样可以大幅减小时间复杂度（相应的，也不用单独建立数组确认国家i是否已走过）。然后是判断部分。这一部分很烦，需要慢慢来。首先建立一个数组存储旅行者已经学习过的所有文化，然后再准备前往国家i前进行检测就行了。注意国家i的文化不能与已学习的任何一种文化相同或排斥。显然任和一条路径的长度均>0，故只要查看路径长度就能判断两个国家间是否有路径。

下面是我的代码：


#include<bits/stdc++.h>
using namespace std;
const int N = 1020;
typedef pair<int, int>PII;
int n, k, m;
int s, t;
struct Node { int w, v; };
vector<Node>e[N];
int dist[N];
int vis[N];
int c[N];
int mp[N][N];
int pre[N];
priority_queue<PII>q;
const int MAXN = 707406378;//最大值 
int solve(int u, int v) {
    int t = u;
    while (t) {
        if (mp[c[v]][c[t]]||c[t] == c[v]) {
            return false;
        }
        t = pre[t];
    }
    return true;
}
void dij(int s) {
    memset(dist, 127 / 3, sizeof(dist));
    dist[s] = 0;
    q.push({ 0,s });
    while (q.size()) {
        auto t = q.top();
        q.pop();
        int u = t.second;
        if (vis[u])continue;
        vis[u] = 1;
        for (auto ed : e[u]) {
            int w = ed.w;
            int v = ed.v;
            if ((dist[v] > dist[u] + w) && solve(u, v)) {
                dist[v] = dist[u] + w;
                pre[v] = u;
                q.push({ -dist[v],v });
            }
        }
    }
}
int main() {
    cin >> n >> k >> m >> s >> t;
    for (int i = 1; i <= n; i++)cin >> c[i];
    for (int i = 1; i <= k; i++) {
        for (int j = 1; j <= k; j++)cin >> mp[i][j];
    }
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        e[a].push_back({ c,b });
        e[b].push_back({ c,a });
    }
    dij(s);
    if (dist[t] ==MAXN)cout << "-1";
    else cout << dist[t];
    return 0;
}

#include<bits/stdc++.h>
using namespace std;

// 定义常量和类型别名
const int N = 1020;          // 最大节点数量
typedef pair<int, int>PII;   // 定义PII为pair<int, int>的别名，用于优先队列

// 全局变量定义
int n, k, m;                 // n:节点数, k:颜色数, m:边数
int s, t;                    // s:起点, t:终点
struct Node { int w, v; };   // 定义边的结构: w为权重, v为目标节点
vector<Node>e[N];            // 邻接表存储图: e[u]表示从u出发的所有边
int dist[N];                 // 存储从起点到各节点的最短距离
int vis[N];                  // 标记节点是否已访问(用于Dijkstra算法)
int c[N];                    // 存储每个节点的颜色: c[i]表示节点i的颜色
int mp[N][N];                // 颜色关系矩阵: mp[i][j]表示颜色i和j是否冲突
int pre[N];                  // 存储路径前驱节点: pre[v] = u表示v的前驱是u
priority_queue<PII>q;        // 优先队列(最大堆)，用于Dijkstra算法
const int MAXN = 707406378;  // 表示一个很大的数，用于初始化距离和判断不可达

/**
 * 检查从起点到u的路径上的所有节点颜色是否与v的颜色冲突
 * @param u 当前节点
 * @param v 要到达的下一个节点
 * @return true表示无冲突，false表示有冲突
 */
int solve(int u, int v) {
    int t = u;
    // 沿着前驱路径回溯，检查所有祖先节点
    while (t) {
        // 如果v的颜色与路径上某个节点的颜色冲突，或者颜色相同
        if (mp[c[v]][c[t]] || c[t] == c[v]) {
            return false;  // 存在冲突，返回false
        }
        t = pre[t];  // 继续回溯前一个节点
    }
    return true;  // 无冲突，返回true
}

/**
 * Dijkstra算法求最短路径，加入了颜色冲突检查
 * @param s 起点
 */
void dij(int s) {
    // 初始化距离数组为一个较大的值(近似无穷大)
    memset(dist, 127 / 3, sizeof(dist));
    dist[s] = 0;  // 起点到自身的距离为0
    q.push({ 0, s });  // 将起点加入优先队列，存储(-距离, 节点)，模拟最小堆

    // 当队列不为空时
    while (q.size()) {
        auto t = q.top();  // 取出队首元素(距离最小的节点)
        q.pop();
        int u = t.second;  // 当前节点

        if (vis[u]) continue;  // 如果已访问过，跳过
        vis[u] = 1;  // 标记为已访问

        // 遍历当前节点的所有邻边
        for (auto ed : e[u]) {
            int w = ed.w;  // 边的权重
            int v = ed.v;  // 目标节点

            // 如果通过当前路径到达v的距离更短，且颜色无冲突
            if ((dist[v] > dist[u] + w) && solve(u, v)) {
                dist[v] = dist[u] + w;  // 更新距离
                pre[v] = u;  // 记录前驱节点
                q.push({ -dist[v], v });  // 加入优先队列(用负数模拟最小堆)
            }
        }
    }
}

int main() {
    // 输入基本参数
    cin >> n >> k >> m >> s >> t;

    // 输入每个节点的颜色
    for (int i = 1; i <= n; i++) {
        cin >> c[i];
    }

    // 输入颜色冲突矩阵
    for (int i = 1; i <= k; i++) {
        for (int j = 1; j <= k; j++) {
            cin >> mp[i][j];
        }
    }

    // 输入边信息，构建邻接表
    for (int i = 0; i < m; i++) {
        int a, b, c;  // a和b为边的两个端点，c为边的权重
        cin >> a >> b >> c;
        e[a].push_back({ c, b });  // 添加双向边
        e[b].push_back({ c, a });
    }

    // 执行Dijkstra算法求最短路径
    dij(s);

    // 输出结果
    if (dist[t] == MAXN) {
        // 如果终点距离仍为初始值，说明不可达
        cout << "-1";
    } else {
        // 否则输出最短距离
        cout << dist[t];
    }

    return 0;
}

代码的主要功能是在一个带权无向图中，求解从起点到终点的最短路径，同时要求路径上的所有节点颜色不能与终点颜色冲突（包括颜色相同也视为冲突）。代码使用了 Dijkstra 算法作为基础，并在松弛操作时加入了颜色冲突检查的逻辑。

洛谷

P1078 [NOIP 2012 普及组] 文化之旅