AtCoder ABC #245 : G - Foreign Friends

時間が合わず不参加。
https://atcoder.jp/contests/abc245/tasks/abc245_g

問題

N人の人とK個の国があり、各人の済む国が与えられる。
また、N人中L人は人気者であり、だれが人気者かが指定される。

ここでM組の人の組み合わせがあり、その2名を友人にするためにかかるコストが与えられる。
各人について、自分の住む国以外の国の人気者と間接的に友人になる最小コストを求めよ。

解法

ダイクストラ法で解く。
各人について、最小コストで仲良くなれる国の人気者とそのコストの上位2位までを求めよう。
各人1位と2位のいずれかは自分の住む国と異なる国の人気者へのコストを示す。

int N,M,K,L;
int A[101010];
int ok[101010];

vector<pair<int,int>> E[202020];
int C[2][202020];
ll D[2][202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>K>>L;
	FOR(i,N) {
		cin>>A[i];
		A[i]--;
		C[0][i]=C[1][i]=K;
		D[0][i]=D[1][i]=1LL<<60;
	}
	priority_queue<pair<ll,int>> Q;
	FOR(i,L) {
		cin>>x;
		x--;
		C[0][x]=A[x];
		D[0][x]=0;
		Q.push({0,x});
	}
	FOR(i,M) {
		cin>>x>>y>>r;
		E[x-1].push_back({y-1,r});
		E[y-1].push_back({x-1,r});
	}
	while(Q.size()) {
		ll co=-Q.top().first;
		int cur=Q.top().second%N;
		int id=Q.top().second/N;
		Q.pop();
		if(D[id][cur]!=co) continue;
		FORR2(e,c,E[cur]) {
			if(D[0][e]>co+c) {
				if(C[0][e]!=C[id][cur]) {
					C[1][e]=C[0][e];
					D[1][e]=D[0][e];
					Q.push({-D[1][e],e+N});
				}
				D[0][e]=co+c;
				C[0][e]=C[id][cur];
				Q.push({-D[0][e],e});
			}
			else if(D[1][e]>co+c&&C[id][cur]!=C[0][e]) {
				C[1][e]=C[id][cur];
				D[1][e]=co+c;
				Q.push({-D[1][e],e+N});
			}
		}
	}
	
	FOR(i,N) {
		ll a=(A[i]==C[0][i])?D[1][i]:D[0][i];
		if(a>=1LL<<60) a=-1;
		cout<<a<<" ";
	}
	cout<<endl;
}

まとめ

他にもlog(K)回ダイクストラ回すとかいろいろな方法があるみたいね。