讨论/算法和数据结构/最短时间路径问题/
最短时间路径问题

问题描述
乐乐要参加地区程序设计竞赛。明天一大早,她必须从 Tuttlingen 赶到 Freiburg 。因为担心到的太晚被拒绝参赛,她开始查找能让她尽早到达 Freiburg 的乘车方案。不过她又不愿意太早去车站,所以如果有几种方案能同时到达目的地,她会选择出发时间最晚的。

乐乐希望你能帮助她解决这个问题,并能让她明天早上多睡会儿。现在给你的是一份列车时刻表。你必须计算出最早到达目的地的方案中最晚出发的一个方案。有一件神奇的事情是:乐乐很善于转车,她能瞬间转车,即转车需要的时间是 0 。

输入格式
输入包含一组或多组数据,每组数据都由三部分组成。

第一部分是这条铁路线上列车连接的所有城市的名字。它从包含一个正整数 C(<=100) 的一行开始,接下来 C 行每行列出一个城市的名字,城市的名字是由字母组成一个单词。C=0表示输入的结束。

第二部分描述当天这条铁路线的列车时刻表。它从包含一个正整数 T(<=1000) 的一行开始,接下来是 T 列火车的时刻表。每列火车的时刻表从包含一个正整数 ti(<=100) 的一行开始,接下来 ti 行,每行包含一个时刻和一个城市名,表示旅客可以在那个城市那个时刻上下车。时刻是用 24 小时格式 hhmm 给出的。

第三部分有 3 行:第一行是最早可能的出发时刻,第二行是乐乐出发的城市,第三行是目的地,这两个城市是不同的。

输出格式
对每组数据,输出一行“Scenario #n”,其中 n 是该组数据的序号。

如果存在到达的方案,输出该方案的出发时间地点和到达时间地点,输出必须如样例显示的那样对齐,不足的补上空格。如果没有能当天到达(即午夜以前到达)的方案,那么输出“No connection”。

每组数据后面输出一个空行。

样例输入
3
Tuttlingen
Constance
Freiburg
3
2
0949 Tuttlingen
1006 Constance
2
1325 Tuttlingen
1550 Freiburg
2
1205 Constance
1411 Freiburg
0800
Tuttlingen
Freiburg
2
Ulm
Vancouver
1
2
0100 Ulm
2300 Vancouver
0800
Ulm
Vancouver
0

样例输出
Scenario #1
Departure 0949 Tuttlingen
Arrival 1411 Freiburg

Scenario #2
No connection

这个题是bfs的题

对于每个城市,定义三个变量,

  • arrival[i]表示最早到达城市i的时间

  • departure[i]表示到达城市i的时间为arrival[i]的前提下,最晚离开出发地的时间

  • visited_city[i]表示是否城市i已经计算过

算法流程:

  1. 特判起始城市,对于起始城市,遍历所有铁路,查询这个铁路是否包含起始城市,如果包含,对于铁路j中比起始城市更晚到达的城市,更新arrival[i]为铁路j到达城市i的时间(如果多条铁路到达城市i需要比较哪个时间短),并且更新departure[i]为铁路j中起始城市的时间,将起始城市的visited_city赋值为true
  2. 循环,直到所有的城市都访问过
    • 遍历所有每被访问过的城市,寻找arrival最小的城市来进行下一轮访问,置visited_city为true
    • 假定这个城市是城市i,遍历所有的铁路,查询这个铁路是否包含城市i,且该铁路到达城市i的时间比arrival[i]晚,如果存在,那么这个铁路中所有比城市i更晚到达的城市需要更新,更新arrival为更早的时刻,如果时刻相同,让departure跟城市i的departure对比,更新为更晚的一个
  3. 最后输出到达城市的arrival和departure即可

整个算法复杂度是o(C*T*max(t[i]))

6