#1742. [语言月赛 202508] 共享航班
[语言月赛 202508] 共享航班
题目描述
扶苏获取了 条航线数据,每条数据都是一个字符串,包括一趟航班的代码、出发地、目的地、起飞时间。一条数据的格式是:
CODE-DEP-DES-HH:MM
其中:
CODE是该航班的代码,该代码是一个长度为 的字符串,前两位是字母,表示所属航司,后四位是数字,是航司给该航班的代号。同一航司的代码前两位相同,不同航司的代码前两位不同,因此可以用航班号前两位来区分和表示航司。例如CA1234,SC9876。DEP是一个长度为 的字符串,表示飞机的出发机场代码。不同机场的代码不同,例如PEK表示北京首都国际机场。DES是一个长度为 的字符串,表示飞机的到达机场代码。不同机场的代码不同,例如PVG表示上海浦东国际机场。HH:MM是一个长度为 的字符串,H和M均是 的数字,表示起飞的小时和分钟,不足两位时补0。例如:09:21表示 点 分。
下面是一个例子:
CA1501-PEK-PVG-08:30
SC5306-PEK-PVG-08:30
ZH2468-PEK-PVG-08:30
CZ1357-PEK-PVG-08:30
MU9197-SHA-TFU-08:00
依次表示:
CA公司售卖的代号为CA1501的航班,从PEK飞往PVG,起飞时间08:30。SC公司售卖的代号为SC5306的航班,从PEK飞往PVG,起飞时间08:30。ZH公司售卖的代号为ZH2468的航班,从PEK飞往PVG,起飞时间08:30。CZ公司售卖的代号为CZ1357的航班,从PEK飞往PVG,起飞时间08:30。MU公司售卖的代号为MU9197的航班,从SHA飞往TFU,起飞时间08:00。
同时,扶苏还知道有些航司之间有联盟关系,每个航司最多属于一个联盟。两条数据是共享航班当且仅当:
- 它们的公司属于同一个联盟。
- 它们起飞、降落机场分别相同。
- 它们起飞时间相同。
可能有多个航班两两之间均构成代码共享关系,此时它们对应同一趟实际航班。
例如,扶苏知道 CA 和 SC 和 ZH 同属于一个联盟,而 CZ 不属于该联盟,所以上面例子里前三条是共享航班,对应同一趟实际的航班,但前三条和第四条不是共享航班。而第五条和前四条信息的起降地、时间均不同,因此也不和前四条构成代码共享关系。上面例子中共有三趟实际的航班。
已知共有 个联盟,属于第 个联盟的航司有 个,其代码(航班号前缀)分别是 。同时给定 条航班信息,你要求出这 条信息对应了多少实际的航班。
注意:
- 可能有航司不属于任何联盟。
- 同一航司在同一时间、同一起降地可能有多条航线数据,此时它们对应同一趟实际航班。
输入格式
第一行是两个整数,表示信息数 和联盟数 。
接下来 行,表示一个联盟的信息,按如下格式输入:
- 首先是一个整数,表示该联盟的航司数 。
- 接下来有 个长度为 的字符串,表示该联盟每个航司的代码(航班号前缀)。
接下来 行,每行一个字符串,表示一条航班信息,其具体格式见【题目描述】部分。
输出格式
输出一行一个整数,表示共有多少个实际航班。
样例
7 2
3 CA ZH SC
2 CZ MF
CA1501-PEK-PVG-08:30
CZ1357-PEK-PVG-08:30
SC5306-PEK-PVG-08:30
ZH2468-PEK-PVG-08:30
MF1357-PEK-PVG-08:30
MU9197-SHA-TFU-08:00
CA9197-SHA-TFU-08:00
4
题目来源:洛谷 B4388