洛谷 P1078 [NOIP2012 普及组] 文化之旅

题意

有一个 $n$ 点 $m$ 边的无向图，每个点都有一个颜色（可能重复），还给定了一个矩阵 $A$。如果经过了颜色为 $i$ 的点，那就不能再经过颜色为 $i$ 的点以及满足 $A_{i,j}=1$ 的颜色为 $j$ 的点。求 $s\to t$ 的最短路，不保证 $A_{i,j}=A_{j,i}$。

思路

由于 $A_{i,j}=A_{j,i}$ 不一定成立，所以不能用并查集维护。考虑到数据范围较小，可以用暴力的做法，记录下路径，在 dijkstra 松弛下一个点前，判断这个点的颜色是否和走过的冲突，有冲突就忽略。

代码

// Problem: P1078 [NOIP2012 普及组] 文化之旅
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1078
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include<iostream>
#include<queue>
using namespace std;
#define int long long
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;signed main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int n, k, m, s, t;cin >> n >> k >> m >> s >> t;s--, t--;vector<int> c(n);for(auto &i: c){cin >> i;i--;}vector<vector<int>> a(k, vector<int>(k));for(auto &i: a)for(auto &j: i) cin >> j;vector<vector<PII>> G(n);for(int i = 0, u, v, w; i < m; i++){cin >> u >> v >> w;u--, v--;G[u].push_back({v, w});G[v].push_back({u, w});}vector<int> dis(n, INF), pre(n, -1);vector<bool> vis(n, false);auto check = [&](int u, int v){int tmp = u;while(tmp != -1){if(a[c[v]][c[tmp]] || c[v] == c[tmp]) return false;tmp = pre[tmp];}return true;};auto dij = [&](int s){priority_queue<PII, vector<PII>, greater<PII>> q;dis[s] = 0;q.push({0, s});while(q.size()){int u = q.top().second;q.pop();if(vis[u]) continue;vis[u] = true;for(auto &edge: G[u]){int v = edge.first, w = edge.second;if(dis[v] > dis[u] + w && check(u, v)){dis[v] = dis[u] + w;pre[v] = u;q.push({dis[v], v});}}}};dij(s);cout << (dis[t] == INF? -1: dis[t]) << endl;return 0;
}