Untitled
davidlayaaa
plain_text
a year ago
2.6 kB
6
Indexable
#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; }
Editor is loading...
Leave a Comment