若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。


  • 运维

  • 前端

  • 编程

  • 随笔

  • hust-oj

1487: 5.4.2 Canada Tour 周游加拿大

发表于 2017-10-06   |   分类于 HUSTOJ   |   阅读次数 1,423

题目描述

你赢得了一场航空公司举办的比赛,奖品是一张加拿大环游机票。旅行在这家航空公司开放的最西边的城市开始,然后一直自西向东旅行,直到你到达最东边的城市,再由东向西返回,直到你回到开始的城市。每个城市只能访问一次,除了旅行开始的城市之外,这个城市必定要被访问两次(在旅行的开始和结束)。你不允许使用其他公司的航线或者用其他的交通工具。 给出这个航空公司开放的城市的列表,和两两城市之间的直达航线列表。找出能够访问尽可能多的城市的路线,这条路线必须满足上述条件,也就是从列表中的第一个城市开始旅行,访问到列表中最后一个城市之后再返回第一个城市。

输入

Line 1: 航空公司开放的城市数 N 和将要列出的直达航线的数量 V。N 是一个不大于 100 的正整数。V 是任意的正整数。 Lines 2..N+1: 每行包括一个航空公司开放的城市名称。城市名称按照自西向东排列。不会出现两个城市在同一条经线上的情况。每个城市的名称都是一个字符串,最多15字节,由拉丁字母表上的字母和数字组成;城市名称中没有空格。 Lines N+2..N+2+V-1: 每行包括两个城市名称(由上面列表中的城市名称组成),用一个空格分开。这样就表示两个城市之间的直达双程航线。

输出

Line 1: 按照最佳路线访问的不同城市的数量 M。如果无法找到路线,输出 1。

样例输入

8 9	
Vancouver		
Yellowknife	
Edmonton
Calgary
Winnipeg
Toronto	
Montreal
Halifax	
Vancouver Edmonton
Vancouver Calgary	
Calgary Winnipeg
Winnipeg Toronto
Toronto Halifax
Montreal Halifax
Edmonton Montreal
Edmonton Yellowknife
Edmonton Calgary

样例输出

7

参考代码

暂无

解析

暂无

hustoj

发表评论 取消回复

邮箱地址不会被公开。 必填项已用*标注

*
*


hoxis wechat
著作权归作者所有
站点更新说明
  • 文章目录
  • 站点概览
若是凉夜已成梦

若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。

1904 日志
6 分类
12 标签
RSS
weibo github twitter facebook

友情链接

Dreams孤独患者 原站点 Skip
© 2017 若是凉夜已成梦
Powered by WordPress | 已运行
Theme By NexT.Mist