首页 > 代码库 > 公路修建
公路修建
洛谷传送门
这道水题告诉了我,堆优化的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 }
公路修建
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。