九度Online Judge解题报告

2024-05-08 16:48

本文主要是介绍九度Online Judge解题报告,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

九度1017:题目如下:

题目描述:
    某省调查乡村交通状况,得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通(但不一定有直接的公路相连,只要能间接通过公路可达即可),并要求铺设的公路总长度为最小。请计算最小的公路总长度。
输入:

    测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 );随后的N(N-1)/2行对应村庄间的距离,每行给出一对正整数,分别是两个村庄的编号,以及此两村庄间的距离。为简单起见,村庄从1到N编号。
    当N为0时,输入结束,该用例不被处理。

输出:

    对每个测试用例,在1行里输出最小的公路总长度。

样例输入:
3
1 2 1
1 3 2
2 3 4
4
1 2 1
1 3 4
1 4 1
2 3 3
2 4 2
3 4 5
0
样例输出:
3
5
简单分析一下:这题就是求最短路径,或者说,是求最小生成树的,我是用Prim算法AC的,先上代码再说:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>const int N = 100;
const int MaxInt = 99999999;int map[100][100], low[100], visited[100], n;int prim()
{int i, j, min, pos;int result = 0;memset(low, 0, sizeof(low));memset(visited, 0, sizeof(visited));visited[1] = 1;   pos = 1;for(i = 1; i <= n; i++)if(i != pos)low[i] = map[pos][i];for(i = 1; i < n; i++){min = MaxInt;for(j = 1; j <= n; j++)if(visited[j] == 0 && min > low[j]){min = low[j];pos = j;}visited[pos] = 1;result += min;for(j = 1; j <= n; j++)if(visited[j] == 0 && low[j] > map[pos][j])low[j] = map[pos][j];}min = 0;return result;
}int main()
{int i, j, s, e, w, m;while(~scanf("%d", &n)){if(n == 0)break;m = n*(n-1)/2;for(i = 1; i <= n; i++)for(j = 1; j <= n; j++)map[i][j] = MaxInt;for(j = 1; j <= m; j++){scanf("%d %d %d", &s, &e, &w);map[s][e] = map[e][s] = w;}printf("%d\n", prim());}//system("pause");return 0;
}
好了,接下来该我吐槽了,真不知道这Judge是怎么搞得,注意到我用的全局变量那些数组了吗,其中的100是我const的常量,但是如是:map[N][N]却一直报错,我真搞不懂我是哪里错了,大神Judge能给指点一下吗?非得逼我改成确定的100才行,话说我那时const过的啊!!!!!!

这篇关于九度Online Judge解题报告的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/970877

相关文章

【专题】2024飞行汽车技术全景报告合集PDF分享(附原数据表)

原文链接: https://tecdat.cn/?p=37628 6月16日,小鹏汇天旅航者X2在北京大兴国际机场临空经济区完成首飞,这也是小鹏汇天的产品在京津冀地区进行的首次飞行。小鹏汇天方面还表示,公司准备量产,并计划今年四季度开启预售小鹏汇天分体式飞行汽车,探索分体式飞行汽车城际通勤。阅读原文,获取专题报告合集全文,解锁文末271份飞行汽车相关行业研究报告。 据悉,业内人士对飞行汽车行业

计算机毕业设计 大学志愿填报系统 Java+SpringBoot+Vue 前后端分离 文档报告 代码讲解 安装调试

🍊作者:计算机编程-吉哥 🍊简介:专业从事JavaWeb程序开发,微信小程序开发,定制化项目、 源码、代码讲解、文档撰写、ppt制作。做自己喜欢的事,生活就是快乐的。 🍊心愿:点赞 👍 收藏 ⭐评论 📝 🍅 文末获取源码联系 👇🏻 精彩专栏推荐订阅 👇🏻 不然下次找不到哟~Java毕业设计项目~热门选题推荐《1000套》 目录 1.技术选型 2.开发工具 3.功能

Python:豆瓣电影商业数据分析-爬取全数据【附带爬虫豆瓣,数据处理过程,数据分析,可视化,以及完整PPT报告】

**爬取豆瓣电影信息,分析近年电影行业的发展情况** 本文是完整的数据分析展现,代码有完整版,包含豆瓣电影爬取的具体方式【附带爬虫豆瓣,数据处理过程,数据分析,可视化,以及完整PPT报告】   最近MBA在学习《商业数据分析》,大实训作业给了数据要进行数据分析,所以先拿豆瓣电影练练手,网络上爬取豆瓣电影TOP250较多,但对于豆瓣电影全数据的爬取教程很少,所以我自己做一版。 目

开题报告中的研究方法设计:AI能帮你做什么?

AIPaperGPT,论文写作神器~ https://www.aipapergpt.com/ 大家都准备开题报告了吗?研究方法部分是不是已经让你头疼到抓狂? 别急,这可是大多数人都会遇到的难题!尤其是研究方法设计这一块,选定性还是定量,怎么搞才能符合老师的要求? 每次到这儿,头脑一片空白。 好消息是,现在AI工具火得一塌糊涂,比如ChatGPT,居然能帮你在研究方法这块儿上出点主意。是不

【干货分享】基于SSM的体育场管理系统的开题报告(附源码下载地址)

中秋送好礼 中秋佳节将至,祝福大家中秋快乐,阖家幸福。本期免费分享毕业设计作品:《基于SSM的体育场管理系统》。 基于SSM的体育场管理系统的开题报告 一、课题背景与意义 随着全民健身理念的深入人心,体育场已成为广大师生和社区居民进行体育锻炼的重要场所。然而,传统的体育场管理方式存在诸多问题,如资源分配不均、预约流程繁琐、数据统计不准确等,严重影响了体育场的使用效率和用户体验。

[SWPUCTF 2021 新生赛]web方向(一到六题) 解题思路,实操解析,解题软件使用,解题方法教程

题目来源 NSSCTF | 在线CTF平台因为热爱,所以长远!NSSCTF平台秉承着开放、自由、共享的精神,欢迎每一个CTFer使用。https://www.nssctf.cn/problem   [SWPUCTF 2021 新生赛]gift_F12 这个题目简单打开后是一个网页  我们一般按F12或者是右键查看源代码。接着我们点击ctrl+f后快速查找,根据题目给的格式我们搜索c

【中国国际航空-注册/登录安全分析报告】

前言 由于网站注册入口容易被黑客攻击,存在如下安全问题: 1. 暴力破解密码,造成用户信息泄露 2. 短信盗刷的安全问题,影响业务及导致用户投诉 3. 带来经济损失,尤其是后付费客户,风险巨大,造成亏损无底洞 所以大部分网站及App 都采取图形验证码或滑动验证码等交互解决方案, 但在机器学习能力提高的当下,连百度这样的大厂都遭受攻击导致点名批评, 图形验证及交互验证方式的安全性到底如

hdu1879(解题报告)

继续畅通工程                                   Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

hdu2033(解题报告)

人见人爱A+B                                   Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

HDU3791(解题报告)

二叉搜索树                      Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)                                          Total Subm