oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

walk Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

walk.html

Problem Description

Rar wants to go out for a walk. The town he lives in can be described as a graph, with N intersections and R roads connecting them. Each road i connects intersection Ai and Bi, and has a length of Li kilometers.

Rar lives at intersection 0. He is planning his walk, and wants to ask Q queries in the form: is there a path I can take such that I will arrive at intersection X after walking K kilometers?

Rar is allowed to travel on a road, or arrive at an intersection more than once, but he cannot switch directions in the middle of a road. In other words, once Rar has started on a road, he cannot stop until he reaches the other intersection.

Input

The first line of input will contain three integers, N, R and Q.

The next R lines will describe a graph, with each line i containing Ai, Bi and Li.

The next Q lines will contain two integers each, X and K for that query.

Output

The output should contain Q lines, with each line stating "YES" or "NO", depending whether such a path is possible.

Limits

0 ≤ X, Ai ≠ Bi < N.

Subtask 1 (13%): 1 ≤ N, R ≤ 1000, Li = 1, 0 ≤ K ≤ 104, 1 ≤ Q ≤ 106.

Subtask 2 (23%): 1 ≤ N, R ≤ 1000, 1 ≤ Li ≤ 100, 0 ≤ K ≤ 104, 1 ≤ Q ≤ 106.

Subtask 3 (12%): 1 ≤ N, R ≤ 1000, 1 ≤ Li ≤ 100, 0 ≤ K ≤ 109, 1 ≤ Q ≤ 106.

Subtask 4 (16%): 1 ≤ N, R ≤ 30000, 1 ≤ Li ≤ 100, 0 ≤ K ≤ 109, Q = 1.

Subtask 5 (15%): 1 ≤ N, R ≤ 30000, Li = 1, 0 ≤ K ≤ 109, 1 ≤ Q ≤ 106.

Subtask 6 (21%): 1 ≤ N, R ≤ 30000, 1 ≤ Li ≤ 100, 0 ≤ K ≤ 109, 1 ≤ Q ≤ 106.

Subtask 7 (0%): Sample Testcases.

Sample Testcase 1

Input

3 3 4
0 1 3
0 2 1
1 2 1
1 3
1 2
1 5
2 2

Output

YES
YES
YES
NO

Sample Testcase 2

Input

4 3 3
0 1 2
0 2 4
2 3 1
2 8
2 7
3 5

Output

YES
NO
YES

Tags

Graph Theory

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
113202s256MBMinimum
223422s256MBMinimum
312622s256MBMinimum
416202s256MBMinimum
515402s256MBMinimum
6211222s256MBMinimum
7022s256MBMinimum

Judge Compile Command

g++-8 ans.cpp -o walk -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.