| 题目名称 | 911. [IOI 1993][USACO]周游加拿大 |
|---|---|
| 输入输出 | tourus.in/out |
| 难度等级 | ★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 11 |
| 题目来源 |
 sywgz
于2012-07-12加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：45， 提交：127， 通过率：35.43% | ||||
 521 |
100 | 0.000 s | 0.00 MiB | C++ |
 dateri |
100 | 0.000 s | 0.00 MiB | C++ |
 HZOI_蒟蒻一只 |
100 | 0.000 s | 0.00 MiB | C++ |
 Hzoi_QTY |
100 | 0.000 s | 0.00 MiB | C++ |
 BaDBoY |
100 | 0.000 s | 0.00 MiB | C++ |
 _Itachi |
100 | 0.004 s | 8.28 MiB | C++ |
 Qw |
100 | 0.005 s | 0.36 MiB | C++ |
 forever |
100 | 0.005 s | 0.39 MiB | C++ |
 小DOTA |
100 | 0.005 s | 3.41 MiB | C++ |
 Mayuri |
100 | 0.005 s | 4.36 MiB | C++ |
| 关于 周游加拿大 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
加了stl还0ms……我的脸全用这了……
HZOI_蒟蒻一只
2017-06-09 20:04
6楼
| ||||
|
mdzz
打dfs打了半天连样例都输出不出来  Hzoi_Mafia
2017-06-01 11:33
5楼
| ||||
|
。。我判断无方案return 1结果输出答案时输出的ans+2（为了方便计算1和n）。。
_Itachi
2017-01-06 17:41
4楼
| ||||
|
“如果无法找到路线，输出 1“......
 liu_runda
2016-09-20 15:38
3楼
| ||||
|
| ||||
|
这个特判就清爽多了
 | ||||
cstdio
USACO/tour(译 by Felicia Crazy)
描述
你赢得了一场航空公司举办的比赛，奖品是一张加拿大环游机票。旅行在这家航空公司开放的最西边的城市开始，然后一直自西向东旅行，直到你到达最东边的城市，再由东向西返回，直到你回到开始的城市。每个城市只能访问一次，除了旅行开始的城市之外，这个城市必定要被访问两次（在旅行的开始和结束）。你不允许使用其他公司的航线或者用其他的交通工具。
给出这个航空公司开放的城市的列表，和两两城市之间的直达航线列表。找出能够访问尽可能多的城市的路线，这条路线必须满足上述条件，也就是从列表中的第一个城市开始旅行，访问到列表中最后一个城市之后再返回第一个城市。
PROGRAM NAME: tourus
INPUT FORMAT
| Line 1: | 航空公司开放的城市数 N 和将要列出的直达航线的数量 V。N 是一个不大于 100 的正整数。V 是任意的正整数。 |
| Lines 2..N+1: | 每行包括一个航空公司开放的城市名称。城市名称按照自西向东排列。不会出现两个城市在同一条经线上的情况。每个城市的名称都是一个字符串，最多15字节，由拉丁字母表上的字母组成；城市名称中没有空格。 |
| Lines N+2..N+2+V-1: | 每行包括两个城市名称（由上面列表中的城市名称组成），用一个空格分开。这样就表示两个城市之间的直达双程航线。 |
OUTPUT FORMAT
| Line 1: | 按照最佳路线访问的不同城市的数量 M。如果无法找到路线，输出 1。 |
SAMPLE INPUT (file tourus.in)
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
SAMPLE OUTPUT (file tourus.out)
7
也就是: Vancouver, Edmonton, Montreal, Halifax, Toronto, Winnipeg, Calgary, 和 Vancouver （回到开始城市，但是不算在不同城市之内）。