Untitled

#include <iostream>
using namespace std;
#define INF 1000000;
const int SIZE = 1000;
int a[101][101];
int k[SIZE], p[SIZE], n;
bool vt[SIZE];

int minKey() {
	int min = INF;
	int cur = -1;
	for(int i = 0; i < n; i++) {
		if (!vt[i] && min > k[i]) {
			min = k[i];
			cur = i;
		}

	}
	return cur;
}

void Prim(int st) {
	for(int i = 0; i < n; i++) {
		k[i] = INF;
		p[i] = -1;
		vt[i] = false;
	}
	k[st] = 0;
	for(int i = 0; i < n; i++) {
		int u = minKey();
		vt[u] = true;
		for(int j = 0; j < n; j++) {
			if (!vt[j] && a[u][j] < k[j]) {
				k[j] = a[u][j];
				p[j] = u;
			}
		}
	}
}

int main() {
	//freopen("input.txt", "r", stdin);
	int t;
	cin>>t;
	for(int tc = 1; tc <= t; tc++) {
		cin>>n;
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				cin>>a[i][j];
			}
		}
		Prim(0);
		int result = 0;
		for(int i = 0; i < n; i++) {
			result += k[i];
		}
		cout<<"Case #"<<tc<<endl;
		cout<<result<<endl;
	}
	return 0;
}

#include <iostream>
using namespace std;
int n, val[201][3], b[201];
int a[201][201];
const int INF = 100000;
bool c[201];


int sqrt(int n) {
	int res = 0;
	for(int i = 1; i * i <= n; i++) {
		res = i;
	}
	return res;
}

void calculator_matrix() {
	for(int i = 0; i < n; i++) {
		for(int j = i+1; j < n; j++) {
			int gt = ((val[i][0] - val[j][0]) * (val[i][0] - val[j][0])) + ((val[i][1] - val[j][1]) * (val[i][1] - val[j][1]));
			int check1 = (40 + val[i][2] + val[j][2]) * (40 + val[i][2] + val[j][2]);
			int check2 = (90 + val[i][2] + val[j][2]) * (90 + val[i][2] + val[j][2]);
			if (gt <= check1)
				a[i][j] = a[j][i] = 1;
			else if (gt <= check2 && gt > check1)
				a[i][j] = a[j][i] = 200;
			else
				a[i][j] = a[j][i] = INF;
		}
	}
}

void reset() {
	for(int i = 0; i < n; i++) {
		b[i] = INF;
		c[i] = false;
		for(int j = 0; j < n; j++) {
			a[i][j] = INF;
		}
	}
}

void dijkstra() {
	int p = 0, q = n-1, k = 0;
	b[p] = 0;
	c[p] = true;
	while(!c[q]) {
		for(int i = 0; i < n; i++) {
			if (!c[i] && b[i] > a[k][i] + b[k]) {
				int temp = a[k][i];
				b[i] = temp + b[k];
			}
		}
		k = q;
		for(int i = 0; i < n; i++) {
			if (!c[i] && b[i] < b[k]) {
				k = i;
			}
		}
		c[k] = true;
	}
	if (b[q] == INF) {
		cout<<-1<<endl;
	} else {
		cout<<b[q] / 200<<" "<<b[q] % 200<<endl;
	}
}

int main() {
	freopen("input.txt", "r", stdin);
	int t;
	cin>>t;
	for(int tc = 1; tc <= t; tc++) {
		cin>>n;
		for(int i = 0; i < n; i++) {
			cin>>val[i][0]>>val[i][1]>>val[i][2];
		}
		reset();
		calculator_matrix();
		dijkstra();
	}
	return 0;
}