ある \(2\) 人を間接的に友達にするのに必要な最小コストは、人を頂点、友達にできる関係を辺とみなして作ったグラフにおける頂点間の最短距離と言い換えることができます。

解法の基本となるのはDijkstra法です。 これを \(2\) 段階に分けて変化させます。

Step1: 始点が複数の時のDijkstra法

まず、「自分と異なる国に属する」という条件を除いて、各人について人気者と間接的に友達になるための最小コストを求める方法を考えてみます。

シンプルな解法としては、人気者それぞれに対して、その人気者が他の人と間接的に友達になるための最小コストを求め、その最小値を取ればよいですが、これでは 計算量が \(\Theta(LN\log M)\) または \(\Theta(L(M+N\log N))\) 程度かかってしまい間に合いません。

ここで、仮想頂点 \(S\) を \(1\) つ取り、\(S\) から \(L\) 人の人気者に対応する頂点に対してコスト \(0\) の辺を張ることで、求めたいものは 頂点 \(S\) からそれぞれの頂点に対する最短距離という形で求めることができます。

Step2: 各頂点を複数回調べるDijkstra法

さて、「自分と異なる国に属する」という条件を付加した問題を解くことを考えます。「頂点集合」のうち「始点からの距離」が最も近い頂点から順に確定させていくのが通常のDijkstra法ですが、これを「（国 \(i\) 、人 \(j\) ）のペアの集合」のうち「国 \(i\) に属する人気者が人 \(j\) と間接的に友達となるための最小コスト」が小さいものから順に確定させていくことで同様に解くことができます。しかし、これをそのまま実装すると計算量は \(\Theta(KN\log KM)\) または \(\Theta(K(M+N\log KN))\) となってしまいます。

しかし、ここでそれぞれの 人 \(j\) について、「（国 \(i\) 、人 \(j\) ）のペアの集合」のうち「国 \(i\) に属する人気者が人 \(j\) と間接的に友達となるための最小コスト」が小さい方から \(2\) つ分かれば十分です。この国を \(i_1\), \(i_2\) \((i_1\neq i_2)\)とすると、人 \(j\) は必ず\(i_1\), \(i_2\) の少なくとも一方には属しておらず、また、\(S\) からある頂点までのパスとして短い方から \(3\) 番目以降のものを含む経路が\(S\) から他の頂点へのパスとして \(2\) 番目以内に入ってくることはないからです。 このとき各頂点は \(2\) 回までしか調べられないため、計算量は二分木を用いた優先度付きキューで \(O(N\log M)\) となります。

よって、この問題を解くことができました。

c++による実装例 :

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

int main() {
	int n, m, k, l;
	int u, v, sz;
	long long c;
	cin >> n >> m >> k >> l;

	vector<int>a(n);
	vector<vector<pair<int, long long> > >e(n);
	vector<int>cnt(n, 0);
	vector<long long>d(n, -1);
	vector<int>country(n);
	vector<long long>d2(n, -1);
	priority_queue<tuple<long long, int, int> >pq;

	for (int i = 0; i < n; i++)cin >> a[i];
	for (int i = 0; i < l; i++) {
		cin >> u;
		pq.push({ 0LL,u - 1,a[u - 1] });
	}
	for (int i = 0; i < m; i++) {
		cin >> u >> v >> c;
		e[u - 1].push_back({ v - 1,c });
		e[v - 1].push_back({ u - 1, c });
	}
	while (!pq.empty()) {
		auto[z, x, y] = pq.top();
		pq.pop();
		if (cnt[x] == 0) {
			d[x] = -z;
			country[x] = y;
		}
		else if ((cnt[x] == 1) && (y != country[x])) {
			d2[x] = -z;
		}
		else continue;
		cnt[x]++;
		sz = e[x].size();
		for (int i = 0; i < sz; i++)pq.push({ z - e[x][i].second,e[x][i].first,y });
	}
	for (int i = 0; i < n; i++) {
		if (a[i] != country[i])cout << d[i];
		else cout << d2[i];
		if (i < (n - 1))cout << " ";
		else cout << endl;
	}
	return 0;
}