题目：Codeforces Round #234 D.
Dima and Bacteria
题目链接：http://codeforces.com/contest/400/problem/D
题目意思：有n个病菌分为k个种类，n个病菌编号为1-n，k个种类编号为1-K。把能量从一个细菌运送到另一个细菌需要消耗代价x。问题有两问：1、同一种类任意两个细菌运送能量消耗是否为零。2、不同种类之间最小消耗。
解题思路：英语是硬伤啊！一开始没读懂，看了好久也没明白要干什么。看了题解，发现是并查集 + Floyd，然后就一目了然了……哎~~太弱啊……
程序代码：比大神的长了好多……慢了好多……不多自己看着清晰……
//发现了一个大神并查集封装成类的代码 感觉挺好的也封起来
class DJset {
int *f;
public : DJset(int n){
f = new int[n];
for(int i = 0; i <= n; i ++) f[i] = i;
}
void insert(int i, int j){
int a = getFather(i);
int b = getFather(j);
a > b ? f[a] = b : f[b] = a;
}
int getFather(int i){ return f[i] == i ? i : getFather(f[i]);}
};
DJset *ds;
void build(){
int N = 0;
repf(i, 1, k) {
int num = a[i];
if(a[i] == 1) dis[i][i] = 0;
while( num --){
chg[++N] = i;
}
}
}
//图论好弱啊……
void floyd(){
int a, b, c;
repf(a, 1, k) repf(b, 1, k) repf(c, 1, k)
dis[b][c] = min( dis[b][c], dis[b][a] + dis[a][c]);
repf(a, 1, k) {
repf(b, 1, k){
if(b != 1) cout << ' ';
if(dis[a][b] < 100000) cout << dis[a][b];
else cout << -1 ;
}
cout << endl;
}
}
int solve(){
int u, v, x, N = 1;
int ans = 1;
repf(i, 1, m) {
cin >> u >> v >> x;
if(x == 0 ) ds->insert(u, v);
dis[chg[u]][chg[v]] = dis[chg[v]][chg[u]] = min(dis[chg[v]][chg[u]], x);
}
repf(i, 1, k){
int w = a[i];
int temp = ds->getFather(N);
while( w --) {
//cout << temp << ' ' << ds->getFather(N) << endl ;
if(temp != ds->getFather(N++)) ans = 0;
}
}
if(ans) cout << "Yes" << endl, floyd();
else cout << "No" << endl;
return 0;
}
int main(){
clr(dis, 63);
ios::sync_with_stdio(false);
cin >> n >> m >> k;
ds = new DJset(n);
repf(i, 1, k) cin >> a[i];
build();
//repf(i, 1, n) cout << chg[i] << ' ' ; cout << endl;
solve();
//system("pause");
return 0;
}