2006年安徽省安联杯信息学奥林匹克竞赛第二试试题
标签：信息学
2006年安徽省安联杯信息学奥林匹克竞赛AHOI2006第二试试题
题目
1、上学路线（Route）
可可和卡卡家住合肥市的东郊，每天上学他们都要转车多次才能到达市区西端的学校。直到有一天他们两人参加了学校的信息学奥林匹克竞赛小组才发现每天上学的乘车路线不一定是最优的。
可可：“很可能我们在上学的路途上浪费了大量的时间，让我们写一个程序来计算上学需要的最少时间吧！”
合肥市一共设有N个公交车站，不妨将它们编号为1…N的自然数，并认为可可和卡卡家住在1号汽车站附近，而他们学校在N号汽车站。市内有M条直达汽车路线，执行第i条路线的公交车往返于站点pi和qi之间，从起点到终点需要花费的时间为ti。(1<=i<=M, 1<=pi, qi<=N)
两个人坐在电脑前，根据上面的信息很快就编程算出了最优的乘车方案。然而可可忽然有了一个鬼点子，他想趁卡卡不备，在卡卡的输入数据中删去一些路线，从而让卡卡的程序得出的答案大于实际的最短时间。而对于每一条路线i事实上都有一个代价ci：删去路线的ci越大卡卡就越容易发现这个玩笑，可可想知道什么样的删除方案可以达到他的目的而让被删除的公交车路线ci之和最小。
【2006年安徽省安联杯信息学奥林匹克竞赛第二试试题】相关文章：
来源：查字典奥数网
相关文章
网友关注
网友关注视频
精品推荐
分类导航
杯赛竞赛类别
最新文章
- 太原小学奥数第二讲—有余除法
- 太原小学奥数第一讲—找规律
- 武汉楚才作文登报作品《一件“伟大”事》
- 武汉楚才作文登报作品《又是一年银耳飘香》
- 武汉楚才作文登报作品《芬芳何处寻》
- 武汉楚才作文登报作品《我总想着这些事》
热门推荐
- 合肥市28届青少年信息学（计算机）竞赛获奖名单（小学组）
- 屯小13名选手参加包河区第四届青少年信息学计算机竞赛
- NOIP2013普及组初赛答案
- 2013全国青少年信息学奥林匹克竞赛时间日程
- 合肥中小学生参加信息学奥赛有哪些好处？
- 信息学竞赛Pascal语言 数组与字符串（五）
随机推荐
- 合肥市“讯飞”杯信息学竞赛（小学组）考试大纲
- 青少年信息学竞赛对小升初的作用？
- 合肥市青少年信息学竞赛（小学组）大纲
- 合肥市讯飞杯青少年信息学竞赛规则（小学组）
- 全国青少年信息学（计算机）奥林匹克联赛初赛内容
- 全国青少年信息学（计算机）奥林匹克联赛题型