You are employed by a travel agency and your manager Anna wants to prepare a list of hotels to include in her new travel guide. Her guide contains one entry per station of the metropolitan network. Anna notices that some stations do not have a convenient location with respect to the distance to the three POIs and therefore her guide should not contain a hotel section for such "useless" stations.
Anna considers that a station is useless when another station is closer to all the POIs. Formally a station A is useless when there exists another station B such that B is at least as close to the three POIs as A is and B is strictly closer than A to at least one of those POIs. A station is useful if it is not useless.
Anna asks you how many stations in her guide will have a hotel section. To compute this list you are given the plan of the metropolitan network. The plan of the metropolitan network is an undirected weighted graph. In this graph, each node corresponds to a station (note that each POI is also a station); each edge links two stations and takes a certain time to be traversed in either direction. This graph is connected and the distance between any two stations is the lowest total time of a path between the two nodes.
The input comprises several lines, each consisting of integers separated with single spaces:
In the graph:
Limits
The output should consist of a single line, whose content is an integer, the number of useful stations.
5 4 0 3 1 1 3 1 2 3 1 4 3 1
4
5 6 0 3 1 1 3 1 2 3 1 4 3 1 0 1 1 0 2 1
3
Explanation of Sample 1:
Explanation of Sample 2:
In this graph (depicted on the bottom), three stations are useful: Orly, Disneyland, and Notre-Dame. The stations corresponding to Orly, Disneyland, Notre-Dame are the closest stations to themselves. All stations have a POI at distance 2 except for Gare du Nord, which is at distance 1 to all POIs, and Orly which is at distance 1 to all POIs but at a distance of 0 to itself. Therefore Gare du Nord is useless.
Название |
---|