Moonlight Fox
Time limit1sMemory limit512 MB
Count vertices where the fox's shortest-path distance is strictly less than the minimum binary-modulated walk time from 1, computed with a run/walk parity state graph.
- Level
Medium7 of 10
- Topics
- Graph, Shortest path, Dynamic programming
- Solved
- No attempts yet
Statement
At the foot of Gwanaksan lives a moonlight fox waiting for the full moon. When the moonlight fox bathes in the full moon's light, it can transform into a beautiful nine-tailed fox. But the moonlight fox is not the only one waiting for the full moon. A moonlight wolf also lives there, hoping to become a magnificent werewolf under the moonlight.
Gwanaksan has N tree stumps numbered 1 to N, and M trails run between the stumps. A trail can be walked in either direction, and no two stumps have more than one trail between them. The moonlight fox and the moonlight wolf both live at stump 1.
When the full moon rises, one of the tree stumps receives the moonlight and shines brightly. The moonlight fox and the moonlight wolf must then run along the trails to that stump as fast as possible to claim the moonlight first. The moonlight fox always runs at a constant speed, while the moonlight wolf can run faster than the fox but lacks stamina, so it uses a different strategy. The moonlight wolf runs the first trail at twice the fox's speed, then walks the next trail at half the fox's speed to recover stamina, then runs the following trail again at twice the fox's speed, and repeats this pattern. The moonlight fox and the moonlight wolf each take the route that gets them to the shining stump fastest. Their routes may therefore differ.
The problem setter loves all animals of Gwanaksan, but this time decided to love the moonlight fox a little more. So the moonlight will shine on the stumps where the moonlight fox can arrive before the moonlight wolf. Count how many such stumps there are.
Input
The first line gives two integers N and M, the number of tree stumps and the number of trails (2 ≤ N ≤ 4,000, 1 ≤ M ≤ 100,000).
Each of the following M lines gives three integers a, b, d (1 ≤ a, b ≤ N, a ≠ b, 1 ≤ d ≤ 100,000). This means a trail of length d runs between stump a and stump b.
Output
On the first line, print the number of tree stumps where the moonlight fox can arrive before the moonlight wolf.
Hint
If the moonlight shines on stump 5, the moonlight fox can arrive before the moonlight wolf. If the moonlight shines on stump 4, the moonlight fox and the moonlight wolf arrive at the same time.