原题

题意

在一个无向图上，每个点都有一个颜色。图中有一些被标记为关键点的节点，我们需要对图中每一个点，求出离它最近、且颜色和它不同的关键点的距离。如果不存在这样的关键点，输出 $-1$。

思路

题目需要求多个起点到所有点的最短路，如果对每个关键点单独跑最短路时间爆炸，会超时。

于是我们发现一个重要性质：

所有关键点都是起点，而且我们只需要最短距离，不需要区分来自哪个关键点。

所以可以把所有关键点同时放进队列，只跑一次最短路，就是一道多源 Dijkstra 板子题。

再看题目限制：我们只需要两种不同颜色的最短路就够了。

因为只要有一个和自己颜色不同，就能直接作为答案。

所以每个点最多存两个不同颜色的最短路，多了直接丢掉优化时间空间。

时空复杂度

时间复杂度：$O((n + m) \times \log n)$

空间复杂度：$O(n)$

代码

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

const int N = 1e5 + 5;

struct Node {
  int v, w;
};

struct Edge {
  int u, col;                                       //当前点 u, 颜色 col
  ll w;                                             // 距离 w
  
  bool operator < (const Edge& i) const {
    return w > i.w;                                 // 小根堆：距离小的优先
  }
};

int n, m, k, l, a[N];        // n 点数，m 边数，k 颜色数，l 关键点数
vector<Node> g[N];           // 邻接表存图
vector<Edge> ans[N];         // 每个点保存最多 2 个不同颜色的最短路
priority_queue<Edge> q;

void Dijkstra() {
  while (!q.empty()) {
    auto [u, col, w] = q.top();
    q.pop();
    if (ans[u].size() == 2 || (ans[u].size() == 1 && col == ans[u][0].col)) continue;    // 剪枝：已经存了 2 个颜色 或 当前颜色重复，直接跳过
    ans[u].push_back({u, col, w});
    for (auto &[v, w2] : g[u]) {
      q.push({v, col, w + w2});
    }
  }
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> m >> k >> l;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (int i = 1, x; i <= l; i++) {
    cin >> x;
    q.push({x, a[x], 0});
  }
  for (int i = 1, u, v, w; i <= m; i++) {
    cin >> u >> v >> w;
    g[u].push_back({v, w}), g[v].push_back({u, w});
  }
  Dijkstra();
  for (int i = 1; i <= n; i++) {
    if (ans[i].empty() || (ans[i].size() == 1 && a[i] == ans[i][0].col)) {
      cout << -1 << " ";                                  // 没有答案 或 只有同色答案输出 -1
    } else {
      cout << ans[i][a[i] == ans[i][0].col].w << " ";     // 输出异色答案
    }
  }
  return 0;
}