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

expressways Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

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

expressways.html

Problem Description

There are N cities (numbered 0 to N-1) and R roads connecting them, with the ith road connecting cities Ai and Bi, and requires time Ti to traverse. There are also E expressways, connecting the capital of the country, city 0, with some other city, Ci, and this expressway requires Si time to traverse.

The mayor wishes to remove a subset of expressways such that the minimum time taken to travel from the capital to any other city remains the same. Find out what is the maximum number of expressways he can remove. It is guaranteed that it is possible to travel between any two cities using only normal roads.

Input

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

The next R lines of input will contain three integers each, Ai, Bi and Ti.

The next E lines of input will contain two integers each, Ci and Si.

Output

The first and only line of output should contain a single integer, the maximum number of expressways the mayor can remove.

Limits

For all subtasks: 1 ≤ Ti, Si ≤ 109, 0 ≤ Ai, Bi, Ci < N.

Subtask 1 (37%): 1 ≤ N, R, E ≤ 1000.

Subtask 2 (25%): 1 ≤ N, E ≤ 300000, R = N - 1, Ai = i, Bi = i + 1.

Subtask 3 (38%): 1 ≤ N, R, E ≤ 300000.

Subtask 4 (0%): Sample Testcases.

Sample Input 1

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

Sample Output 1

2

Sample Input 2

5 6 4
0 2 5
0 4 2
2 1 3
1 0 4
1 3 3
2 3 5
2 6
3 7
4 1
1 5

Sample Output 2

3

Tags

Graph Theory

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
137221s256MBMinimum
225211s256MBMinimum
338621s256MBMinimum
4021s256MBMinimum

Judge Compile Command

g++-8 ans.cpp -o expressways -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.