Codeforces 400(#234 Div2 only) D Dima and Bacteria

問題

n匹のバクテリアがいて、(匹?)、1〜nと番号がついている。
最初のc[1]匹が種類1,次のc[2]匹が種類2……で、全部でk種類である。


バクテリアu[i]からv[i]へまたはv[i]からu[i]へ、エネルギーを移すことがx[i]ドルで可能である。
このような関係がm個与えられる。


このとき、同じ種類のバクテリアは必ず無料でエネルギーを移せるかを判定せよ。
移せる場合、i種類目からj種類目までエネルギーを移動するのにかかるコストを隣接行列の形で出力せよ。
移動できないところは-1を出力せよ。

制約条件

n≦10^5
m≦10^5
k≦500
0≦x[i]≦10^4

方針

負のコストがないのでかんたん。
0円で移動できるところをunion-findでまとめる。


で、同じバクテリア同士は同じunionに属していればyes, そうでなければnoを出力すればいい。
コストは、i番目のバクテリアからj番目のバクテリアにうつるコストをd[i][j]として、
(同じバクテリア間は無料で移せることがもう確定したので、d[i][j]は最小のやつを選べばいい)
ワーシャルフロイドすれば、2種類間の最小のコストが全部わかる。

ソースコード

const int MX = 100010;
int p[MX];
int root(int x){
	if(x == p[x]) return x;
	return p[x] = root(p[x]);
}
void merge(int a, int b){
	a = root(a); b = root(b);
	if(a != b) p[b] = a;
}

int n, m, k;
int u[MX], v[MX], x[MX], c[MX], sum[MX];
int d[500][500];

int type(int a){
	return upper_bound(sum, sum + k, a) - sum - 1;
}

int main(){
	cin >> n >> m >> k;
	
	rep(i, k){
		cin >> c[i];
		sum[i + 1] = sum[i] + c[i];
	}
	rep(i, k) rep(j, k) d[i][j] = i == j ? 0 : inf;
	rep(i, n) p[i] = i;
	
	rep(i, m){
		cin >> u[i] >> v[i] >> x[i];
		u[i]--;
		v[i]--;
		
		int t1 = type(u[i]), t2 = type(v[i]);
		//cerr<<t1<<" "<<t2<<endl;
		if(x[i] == 0) merge(u[i], v[i]);
		
		d[t1][t2] = d[t2][t1] = min(d[t1][t2], x[i]);
	}
	
	int idx = 0;
	rep(i, k){
		int r = root(idx);
		rep(j, c[i]){
			if(root(idx++) != r){
				cout << "No" << endl;
				return 0;
			}
		}
	}
	
	rep(c, k) rep(a, k) rep(b, k) d[a][b] = min(d[a][b], d[a][c] + d[c][b]);
	
	cout << "Yes" << endl;
	rep(i, k) rep(j, k) cout << (d[i][j] == inf ? -1 : d[i][j]) << (j==k-1?"\n":" ");
	
	return 0;
}