Ex - Trespassing Takahashi

AtCoder

IDabc250_h

Time7000ms

Memory256MB

Difficulty—

There are $N$ points numbered $1$ through $N$, and $M$ roads. The $i$\-th ($1 \leq i \leq M$) road connects Point $a_i$ and Point $b_i$ bidirectionally and requires $c_i$ minutes to pass through. One can travel from any point to any other point using some number of roads. There is a house on Points $1,\ldots, K$. For $i=1,\ldots,Q$, solve the following problem. > Takahashi is currently at the house at Point $x_i$ and wants to travel to the house at Point $y_i$. > Once $t_i$ minutes have passed since his last sleep, he cannot continue moving anymore. > He can get sleep only at a point with a house, but he may do so any number of times. > If he can travel from Point $x_i$ to Point $y_i$, print `Yes`; otherwise, print `No`. ## Constraints * $2 \leq K \leq N \leq 2 \times 10^5$ * $N-1 \leq M \leq \min (2 \times 10^5, \frac{N(N-1)}{2})$ * $1 \leq a_i \lt b_i \leq N$ * If $i \neq j$, then $(a_i,b_i) \neq (a_j,b_j)$. * $1 \leq c_i \leq 10^9$ * One can travel from any point to any other point using some number of roads. * $1 \leq Q \leq 2 \times 10^5$ * $1 \leq x_i \lt y_i \leq K$ * $1 \leq t_1 \leq \ldots \leq t_Q \leq 10^{15}$ * All values in input are integers. ## Input Input is given from Standard Input in the following format: $N$ $M$ $K$ $a_1$ $b_1$ $c_1$ $\vdots$ $a_M$ $b_M$ $c_M$ $Q$ $x_1$ $y_1$ $t_1$ $\vdots$ $x_Q$ $y_Q$ $t_Q$ [samples]

Samples

Input #1

Output #1

No
Yes
Yes

In the $3$\-rd problem, it takes no less than $13$ minutes from Point $1$ to reach Point $3$ directly. However, he can first travel to Point $2$ in $12$ minutes, get sleep in the house there, and then travel to Point $3$. Thus, the answer is `Yes`.

API Response (JSON)

{
  "problem": {
    "name": "Ex - Trespassing Takahashi",
    "description": {
      "content": "There are $N$ points numbered $1$ through $N$, and $M$ roads. The $i$\\-th ($1 \\leq i \\leq M$) road connects Point $a_i$ and Point $b_i$ bidirectionally and requires $c_i$ minutes to pass through. One ",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 7000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc250_h"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There are $N$ points numbered $1$ through $N$, and $M$ roads. The $i$\\-th ($1 \\leq i \\leq M$) road connects Point $a_i$ and Point $b_i$ bidirectionally and requires $c_i$ minutes to pass through. One ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments