Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <cmath>
- #include <cstring>
- #include <float.h>
- // MST Algoritmo de PRIM
- #define dist(x, x1, y, y1) sqrt(pow(x - x1, 2) + pow(y - y1, 2))
- #define MAX 501
- double grafo[MAX][MAX];
- struct dados
- {
- int x, y;
- }pessoas[MAX];
- double prim(int n) // Tamanho
- {
- double fixo[MAX];
- double custo[MAX];
- double total = 0;
- for(int i = 0; i < n; i++)
- {
- fixo[i] = 0;
- custo[i] = FLT_MAX; // Ou INF se for Inteiro
- }
- custo[0] = 0;
- for(int faltam = n; faltam > 0; faltam--)
- {
- int no = -1;
- for(int i = 0; i < n; i++)
- if(!fixo[i] && (no == -1 || custo[i] < custo[no]))
- no = i;
- fixo[no] = 1;
- if(custo[no] == FLT_MAX)
- {
- total = FLT_MAX;
- break;
- }
- total += custo[no];
- for(int i = 0; i < n; i++)
- if(grafo[no][i] != -1)
- if(custo[i] > grafo[no][i])
- custo[i] = grafo[no][i];
- }
- return total;
- }
- int main()
- {
- int c, n;
- scanf("%d", &c);
- while(c--)
- {
- scanf("%d", &n);
- for(int i = 0; i < n; i++)
- scanf("%d %d", &pessoas[i].x, &pessoas[i].y);
- for(int i = 0; i < n; i++)
- memset(grafo[i], 0xff, sizeof(float) * n);
- for(int i = 0; i < n - 1; i++)
- for(int j = i + 1; j < n; j++)
- grafo[i][j] = grafo[j][i] = dist(pessoas[i].x, pessoas[j].x, pessoas[i].y, pessoas[j].y);
- printf("%.2lf\n", prim(n) / 100.00);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment