这道水题告诉了我，堆优化的prim有时还不如朴素prim快。。。
居然记错时间复杂度了，我也真是菜。
1 #include <cstdio> 2 #include <queue> 3 #include <cmath> 4 5 using namespace std; 6 7 int n; 8 double ans, map[5001][2], minn[5001]; 9 bool vis[5001]; 10 11 inline double dis(int x, int y) 12 { 13 return sqrt((map[x][0] - map[y][0]) * (map[x][0] - map[y][0]) + (map[x][1] - map[y][1]) * (map[x][1] - map[y][1])); 14 } 15 16 inline void queue_prim() 17 { 18 int i, j, k; 19 double l; 20 for(i = 0; i <= n; i++) minn[i] = 99999999; 21 minn[1] = 0; 22 for(i = 1; i <= n; i++) 23 { 24 k = 0; 25 for(j = 1; j <= n; j++) 26 if(!vis[j] && minn[j] < minn[k]) 27 k = j; 28 vis[k] = 1; 29 for(j = 1; j <= n; j++) 30 { 31 l = dis(k, j); 32 if(!vis[j] && l < minn[j]) minn[j] = l; 33 } 34 } 35 for(i = 1; i <= n; i++) ans += minn[i]; 36 } 37 38 int main() 39 { 40 int i; 41 scanf("%d", &n); 42 for(i = 1; i <= n; i++) scanf("%lf %lf", &map[i][0], &map[i][1]); 43 queue_prim(); 44 printf("%.2lf", ans); 45 return 0; 46 }