# PROBLEM ONE: TRAINS
Problem: The local commuter railroad services a number of towns in Kiwiland. Because of monetary concerns, all of the tracks are 'one-way.' That is, a route from Kaitaia to Invercargill does not imply the existence of a route from Invercargill to Kaitaia. In fact, even if both of these routes do happen to exist, they are distinct and are not necessarily the same distance!
The purpose of this problem is to help the railroad provide its customers with information about the routes. In particular, you will compute the distance along a certain route, the number of different routes between two towns, and the shortest route between two towns.
Input: A directed graph where a node represents a town and an edge represents a route between two towns. The weighting of the edge represents the distance between the two towns. A given route will never appear more than once, and for a given route, the starting and ending town will not be the same town.
Output: For test input 1 through 5, if no such route exists, output 'NO SUCH ROUTE'. Otherwise, follow the route as given; do not make any extra stops! For example, the first problem means to start at city A, then travel directly to city B (a distance of 5), then directly to city C (a distance of 4).
1. The distance of the route A-B-C.
2. The distance of the route A-D.
3. The distance of the route A-D-C.
4. The distance of the route A-E-B-C-D.
5. The distance of the route A-E-D.
6. The number of trips starting at C and ending at C with a maximum of 3 stops. In the sample data below, there are two such trips: C-D-C (2 stops). and C-E-B-C (3 stops).
7. The number of trips starting at A and ending at C with exactly 4 stops. In the sample data below, there are three such trips: A to C (via B,C,D); A to C (via D,C,D); and A to C (via D,E,B).
8. The length of the shortest route (in terms of distance to travel) from A to C.
9. The length of the shortest route (in terms of distance to travel) from B to B.
10. The number of different routes from C to C with a distance of less than 30. In the sample data, the trips are: CDC, CEBC, CEBCDC, CDCEBC, CDEBC, CEBCEBC, CEBCEBCEBC.
Test Input:
----------
For the test input, the towns are named using the first few letters of the alphabet from A to D. A route between two towns (A to B) with a distance of 5 is represented as AB5.
Graph: AB5, BC4, CD8, DC8, DE6, AD5, CE2, EB3, AE7
Expected Output:
---------------
Output #1: 9 <br/>
Output #2: 5 <br/>
Output #3: 13 <br/>
Output #4: 22 <br/>
Output #5: NO SUCH ROUTE <br/>
Output #6: 2 <br/>
Output #7: 3 <br/>
Output #8: 9 <br/>
Output #9: 9 <br/>
Output #10: 7 <br/>
没有合适的资源?快使用搜索试试~ 我知道了~
GPC_Prob1_Trains
共5个文件
java:2个
txt:1个
gitignore:1个
3星 · 超过75%的资源 需积分: 6 1 下载量 176 浏览量
2021-04-28
03:51:01
上传
评论
收藏 4KB ZIP 举报
温馨提示
问题一:训练 问题:当地通勤铁路服务于新西兰的许多城镇。 由于金钱的考虑,所有途径都是“单向的”。 也就是说,从凯塔亚到因弗卡吉尔的路线并不意味着存在从因弗卡吉尔到凯塔亚的路线。 实际上,即使这两个路线确实都存在,它们也是截然不同的,并且不一定是相同的距离! 该问题的目的是帮助铁路为其客户提供有关路线的信息。 特别是,您将计算沿特定路线的距离,两个镇之间的不同路线的数量以及两个镇之间的最短路线。 输入:一个有向图,其中一个节点代表一个镇,一条边代表两个镇之间的路线。 边缘的权重表示两个镇之间的距离。 给定的路线永远不会出现超过一次,并且对于给定的路线,起点和终点的城镇将不是同一城镇。 输出:对于测试输入1至5,如果不存在这样的路由,则输出'NO SUCH ROUTE'。 否则,请按照给定的路线行驶; 不要停下来! 例如,第一个问题意味着从城市A开始,然后直接前往城市B(距离为5),然
资源详情
资源评论
资源推荐
收起资源包目录
GPC_Prob1_Trains-master.zip (5个子文件)
GPC_Prob1_Trains-master
src
trains
routes
Main.java 894B
Graph.java 3KB
.gitignore 18B
INPUT.txt 43B
README.md 3KB
共 5 条
- 1
侯戈
- 粉丝: 21
- 资源: 4630
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论1