The minimum cost required to make a person an indirect friend of another can be interpreted as the shortest path on the graph where people are regarded as vertices and the candidates of pairs of friends as edges.

The basic idea of the solution is Dijkstra’s algorithm, which varies in two steps.

Step 1: Dijkstra’s algorithm with multiple sources

First, let’s ignore the condition of “belonging to a different country” and consider how to find the minimum cost required for each people to be an indirect friend of a popular person.

A simple solution is to find, for each fixed popular person, the minimum cost required to become an indirect person for every other people, and find the minimum value. However it costs about \(\Theta(LN\log M)\) time, which does not finish in time.

Here, by adding additional virtual vertex \(S\) and edges from \(S\) to the vertices corresponding to \(L\) popular people, the desired values can be found as the minimum distances from Vertex \(S\) to each vertex.

Step 2: Dijkstra’s algorithm in which each vertex is inspected multiple times

Now, let’s consider the problem in which the condition of “belonging to a different country” is added. Normal Dijkstra’s method determines the “distance from the starting vertex” in the “vertex set” in the increasing order of the distances; by determining “the minimum cost required for each popular person belonging in Country \(i\) to become an indirect friend of Person \(j\)” in the “set of pairs of (Country \(i\), Person \(j\))”, this problem can be solved in a similar way. However, directly implementing this requires a total complexity of \(\Theta(KN\log KM)\) or \(\Theta(K(M+N\log KN))\).

Here, for each person \(j\), among the elements of “the set of pairs of (Country \(i\), Person \(j\))”, it is sufficient to find “the minimum, and the second minimum, cost required for each popular person belonging in Country \(i\) to become an indirect friend of Person \(j\).” This is because, for these two countries \(i_1\) and \(i_2\) \((i_1\neq i_2)\), Person \(j\) does not belong to at least one of \(i_1\) or \(i_2\), and any path from \(S\) to a vertex that contains a sub-path with the third-minimum cost does never contribute to another path from \(S\) to another vertex with the minimum or the second-minimum cost. In this algorithm, each vertex is inspected at most twice, so the time complexity is \(O(N\log M)\) using a priority queue using binary tree.

Therefore, the problem has been solved.

Sample code in C++:

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

#define N 200000
#define INF (ll)1e+18
#define rep(i, n) for(int i = 0; i < n; ++i)
#define pb push_back
#define ll long long
#define pll pair<long long ,long long>


int main() {
	int n, m, k, l;
	int x, y, sz;
	ll z;
	cin >> n >> m >> k >> l;
	vector<int>a(n);
	vector<vector<pair<int, ll> > >e(n);

	vector<int>used(n, 0);
	vector<ll>d(n, INF);
	vector<int>cit(n);
	vector<ll>dd(n, INF);
	priority_queue<tuple<ll, int, int> >pq;
	tuple<ll, int, int>t;

	rep(i, n)cin >> a[i];
	rep(i, l) {
		cin >> x;
		pq.push({ 0LL,x - 1,a[x - 1] });
	}
	rep(i, m) {
		cin >> x >> y >> z;
		e[x - 1].pb({ y - 1,z });
		e[y - 1].pb({ x - 1,z });
	}
	while (!pq.empty()) {
		t = pq.top();
		pq.pop();
		z = get<0>(t);
		x = get<1>(t);
		y = get<2>(t);
		//   cout<<x<<" "<<y<<" "<<z<<endl;
		if ((used[x] >= 0) && (used[x] != y)) {
			if (used[x] == 0) {
				d[x] = -z;
				cit[x] = y;
				used[x] = y;
			}
			else {
				dd[x] = -z;
				used[x] = -1;
			}

			sz = e[x].size();
			rep(i, sz)pq.push({ z - e[x][i].second,e[x][i].first,y });

		}
	}
	rep(i, n) {
		if (d[i] >= INF)d[i] = -1;
		if (dd[i] >= INF)dd[i] = -1;
	}
	rep(i, n) {
		if (a[i] != cit[i])cout << d[i];
		else cout << dd[i];
		if (i < (n - 1))cout << " ";
		else cout << endl;
	}
	return 0;
}