【问题描述】
你现在要为智能汽车负责设计一种很高级的集中管理系统。目的是利用全球信息指导早上从郊区赶往市中心的乘客如何在避免交通堵塞的情况下最好地到达城市中心。
不幸的是，乘客们对城市非常了解，而且相当自私，你不能简单甩给他们一条费时比以前走的还要长的路劲（否则他们会直接无视你的指导），所以只能说服他们改走另外一条长度相同的路径。
城市的道路网络由路口和连接它们的双向道路组成，通过不同的道路所需时间是不同的。所有乘客都会从各自的路口出发，当然不同的乘客出发的路口可能不同。但是所有乘客都会在同一个地点结束他们的旅程，那就是位于路口1的市中心。如果两个乘客试图在相同的时间，从同一方向，开始沿着相同的道路开始移动，就会出现堵塞——你必须避免种情况的。但是，两名乘客可以在同一时间通过同一个路口，或者在不同时间从同一条道路沿同一方向出发。
请确定最多能有多少人能够开车前往市中心而没有堵塞。注意，所有乘客刚好在同一时间从他们所在路口出发，而且乘客只会选择能够最快到达路口1的路径。
在图C.1中，汽车标记了乘客最开始所在的路口，一辆车已经在市中心了。而属于路口4的车辆，可以走通过路口3的红色的线，或者通过路口2蓝色的虚线。但是剩下的两辆车不可能在避免堵塞的前提下前往市中心。所以，在避免堵塞的情况下，最多只有3辆车能够抵达市中心。
【输入格式】
输入只会包含一组数据。第一行是三个正整数n,m,c，其中n(1≤n≤25000)是路口的个数，m(0≤m≤50000)是道路的个数，而c(1≤c≤1000)则是乘客的个数。接下来m行，每行有三个正整数xi,yi,zi来描述一条道路，xi,yi是该道路连接的两个不同的路口，而ti，是开车通过这个道路的时间（两个方向的时间一样）。所有的路口都能够抵达市中心。最后一行的c个数，分别代表了c个乘客出发的路口。
【输出格式】
一个整数，表示在没有堵塞的情况下最多有多少乘客能够抵达市中心。
【样例输入】
3 3 2
1 2 42
2 3 1
2 3 1
2 3
【样例输出】
2
【样例输入】
4 4 5
1 2 5
1 3 4
4 2 5
4 3 6
4 4 4 4 1
【样例输出】
3
【数据规模和约定】
如输入格式所叙。
2009J Subway Timing
就和很多现代化的城市一样，斯德哥尔摩有一个发达的公共交通系统。而斯德哥尔摩的公共交通的核心就是地铁。一份地铁的拓扑地图描述了不同的地铁线路，以及他们之间的连接方式，如下图图。在这个问题，你可以假定一份地铁地图一定是树形的，尽管斯德哥尔摩的地铁并非确实如此，例如图中蓝色和绿色的线路形成了一个环。
地铁的拓扑图并不关心地铁系统的几何性质，比如说不同地铁站之间的距离（以及相应的旅行时间）。比如，斯德哥尔摩的大部分学生都知道，“Tekniska Hogskolan” (皇家理工学院) 和 “Universitetet” (斯德哥尔摩大学)相隔是非常远的，但是在这幅图上却没有体现。
为了使这张地图更为详细，你要写一个程序，计算出任意相邻地铁站之间所需的旅行时间来。幸运的是，那些旅行时间是已知的，所以你不需要自己去测量。但问题是，实际时间是以秒为单位，而写在地图上的时间却只能是以分钟为单位的整数作为实际时间的估计。
一种自然的估计时间的方法可能是简单地将所有的旅行时间往其最近的整数取整。但是这有可能导致巨大的累计误差。在斯德哥尔摩的地图上，这种估计方法可能导致在某些地铁站之间的旅行总时间一个将近15分钟的偏差。为了避免这个，你的程序需要选择一些旅行时间向上取整，其余的向下取整，从而使得点对之间最大的累计误差最小。
输入格式：
输入包含多组数据。每组数据最开始是一个整数N(1≤N≤100)，为地铁站的个数。这n个地铁站用正整数1到n标记。接下来n-1行包含了三个整数a,b,t(1≤a,b≤n,1≤t≤300)，表示地铁站a和站b是相邻的，而且在它们之间旅行的时间花费是t秒。为了简化问题，忽略地铁在地铁站停留的时间。
一行一个整数0，接在最后一组数据后。
输出格式：
对于每组数据，输出数组组号（从1开始），然后输出对相邻地铁站之间的旅行时间进行最优的舍入之后，两两地铁站对中，旅行时间误差的最大值。请按照样例所给的格式。
2004J Air Traffic Contro
为了避免空中相撞，大部分商业航班都被地面航空管制中心使用雷达跟踪其位置来监视。在这个问题，你会被给予一组飞机和一组控制中心的信息，你要计算飞机的监控在控制中心之间是如何分布的，飞机的位置用(x,y)坐标对表示，基于问题的目的，飞机的高度（海拔）被无视掉了。
一个给定的控制中心能够监控的飞机数量因为设备和工作人员改变时刻变化。在任一时刻，每一个控制中心会尽可能地监控更多的飞机，按照如下优先级选择飞机：1.离这个控制中心比较近的优于比较远的。2.如果两架飞机距离控制中心的同样远，那么选择其中往北更远的(y坐标轴正方向)。3.如果两架飞机的距离和y坐标都相同，中心会选择往东更远的（x坐标正方向）。（补充说明：也就是说在距离相同的情况下，先比较y坐标，y坐标大的优先级高，若y坐标依旧相同，x坐标大的优先级高。没有重点）
在任意时刻，每一个控制中心都有一个圆形“控制范围”，其半径等于其所监控的最远的那架飞机的距离。所有在控制范围内的飞机都被该控制中心监控，但是在边界上的飞机有可能或没可能被控制中心监控到，取决于控制中心的容量和以上列出的优先级。
你不会被告知控制中心的位置,取而代之的，对于每个控制中心，你会被告知它当前监控的飞机个数，以及其监控范围边界上的两点，用这些信息，你能计算出控制中心的位置，以及决定哪些飞机被其监控。如果数据包含多种可能的监控范围，你应该选择包含了靠北最远的那架飞机的，通过先选择靠北最远的再选择靠东最远的打破平局（——这段话的意思你可以这么认为：如果有多种可能的控制范围满足输入要求，那么我们这么来比较：将飞机按照y坐标从大到小，y坐标相同的按照x从大到小排序，然后依次考虑，如果有架飞机在控制范围A内，而其不在控制范围B内，则我们会选择A而不是B。注意，若两个控制范围内部的飞机的集合相同，可以任意选择一个，因为其和输出是没有影响的）。
下面这张展示了两个控制中心和四架飞机的图说明了问题。每个控制中心用一个圆形控制区域和这个区域中的两个点表示，用A和B标记。P1，P2，P3，P4标记了四架飞机。在这个例子中，飞机P1和P4都被一个单独的控制中心监视，而P3被两个控制中心监控，但P2却没有被任何一个控制中心监控。
输入描述：
输入包含多组测试数据，每个数据第一行包括两个正整数NP(0<NP<100)和NC(0<NC<10)，分别表示了飞机的个数和控制中心的个数。接下来NP行，每行两个浮点数表示一架飞机的(x,y)坐标。再接下来NC行，每行描述一个控制中心。首先一个0到NP的正整数（闭区间），表示被该控制中心监控的飞机个数，然后两对浮点数表示监控范围边界上的两个位置的(x,y)坐标（两个位置不会相同，而且上面也不会有飞机）。如果两个点之间的距离小于0.00001，你应该将其视为一个点。
输出描述：
对于每组数据，计算出被零个控制中心监控的飞机个数，被一个控制中心监控的飞机个数，等等直到被NC个控制中心监控的飞机个数，输出数据组号，然后接下来NC+1个数，序列中第ith数表示被i-1个控制中心监控的飞机个数。如果某个控制中心不存在相符合的监控范围，那么输出"Impossible"而不是相应的序列。使用样例中给定的输出格式，然后每组数据之后都要输出一个空行。
（关于输出格式，请注意两个空格和行末空格是否存在）
评论