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

delivery Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

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

delivery.html

Problem Description

Rar the cat has been down on pocket money lately. Therefore, he decided to deliver items in order to earn some extra pocket money. Since Rar the cat has a car capable of holding only up to C items, the delivery company he was working for (Fatdex) has allocated C items for him to deliver for the day. The items Fatdex allocated to Rar the cat is described using the following 2 integers, D (destination) and M (money earned). This means that Rar the cat would earn $M if he delivers the item to destination D. Rar the cat will start from location 0 and have to end the day at location 0. Due to this, D ≠ 0 for any item and there will be no 2 item with the same D.

The world Rar the cat lives in can be described using a graph with N interconnected nodes and E edges, with places as nodes and labelled from 0 to N-1 (inclusive). Roads will be edges and there will be a total of E edges, each defined as 3 integers, A, B and V, meaning that the distance from place A to place B is Vm.

However, Rar the cat's car also requires fuel to operate (and fuel costs money). The cost of fuel required to travel a road of distance Vm would be $V. Therefore, you are supposed to find the greatest amount of money (net profit) Rar the cat can earn for the day by optimally choosing the items he delivers as well as the path taken! (If he makes a loss by delivering any combination of the items, his maximum net profit would be when he doesn't deliver anything, $0).

Input

You are to input from standard input.

The first line of input consists of 3 integers, C, N, followed by E.

The following C lines of input will consist of D and M, with each line describing 1 item for delivery.

The subsequent E lines of input will consist of A, B followed by V, with each line describing the roads in between places. There will be no 2 roads between A and B (or B and A).

Output

Output a single integer to standard output, denoting Rar the cat's maximum earning for the day.

Limits

For all subtasks:

  • 0 < C < N
  • 0 ≤ A, B < N
  • 0 < V ≤ 10000
  • 0 < D < N
  • 0 ≤ M ≤ 1000000

Subtask 1 (10%): C ≤ 8, N = C+1, 0 < E ≤ 36

Subtask 2 (18%): C ≤ 8, N ≤ 100, 0 < E ≤ 4950

Subtask 3 (19%): C ≤ 8, N ≤ 10000, 0 < E ≤ 100000

Subtask 4 (23%): C ≤ 13, N ≤ C+1, 0 < E ≤ 91

Subtask 5 (30%): C ≤ 13, N ≤ 10000, 0 < E ≤ 100000

Subtask 6 (0%): As per sample testcases.

Sample Testcase 1

Input:

3 5 6
1 5
3 5
4 25
0 1 3
1 2 2
1 4 9
3 2 1
3 0 2
3 4 5

Output:

17

$17 profit is obtained by choosing to deliver all the items optimally. The cheapest route to deliver all the items and return is 0->1->2->3->4->3->0, which costs $18 ($3+$2+$1+$5+$5+$2). The money earned from making those deliveries is $35 ($5+$5+$25) and thus the net profit is $17 ($35-$18).

Sample Testcase 2

Input:

3 5 6
1 5
3 5
4 5
0 1 3
1 2 2
1 4 9
3 2 1
3 0 2
3 4 5

Output:

2

$2 profit is obtained by choosing to deliver only the first and second item. The cheapest route to deliver them is 0->1->2->3->0, which costs $8 ($3+$2+$1+$2). The money earned from making those deliveries is $10 ($5+$5) and thus the net profit is $2 ($10-$8).

Sample Testcase 3

Input:

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

Output:

4

$4 profit is obtained by only delivering the second item. The cost for delivery is $4 and the money earned is $8, resulting in a net profit of $4.

Sample Testcase 4

Input:

3 5 6
1 3
3 3
4 5
0 1 3
1 2 2
1 4 9
3 2 1
3 0 2
3 4 5

Output:

0

Making any deliveries will incur a loss to Rar the cat. Therefore, the wisest thing to do is to rest at home and earn $0.

Sample Testcase 5

This testcase adheres to the limits of subtask 4 and 5 only.

Input:

11 12 17
1 3
2 9
3 5
4 3
5 7
6 9
7 10
8 10
9 1
10 5
11 20
9 11 1
9 10 2
9 8 5
9 6 5
8 10 6
8 7 3
8 0 5
8 1 1
1 4 1
2 4 4
2 5 8
0 5 3
0 4 2
5 6 7
6 3 3
7 0 8
7 6 2

Output:

36

By selecting to deliver all items except the 3rd item (D=3, M=5), Rar the cat earns $77. He then delivers these items optimally by going in this order: 0 -$3-> 5 -$8-> 2 -$4-> 4 -$1-> 1 -$1-> 8 -$3-> 7 -$2-> 6 -$5-> 9 -$1-> 11 -$1-> 9 -$2-> 10 -$6-> 8 -$1-> 1 -$1-> 4 -$2-> 0. This results in a fuel cost of $41, which translates to a net profit of $36 ($77-$41). This is the most amount of money Rar the cat can earn for this day. Do note that if Rar the cat decides to deliver all the items, he would earn $1 less than optimal ($35) instead.

Sample Testcase 6

This subtask adheres to the limits of subtask 2, 3 and 5 only.

Input:

7 12 17
1 3
2 9
4 3
6 9
8 10
9 1
10 5
9 11 1
9 10 2
9 8 5
9 6 5
8 10 6
8 7 3
8 0 5
8 1 1
1 4 1
2 4 4
2 5 8
0 5 3
0 4 2
5 6 7
6 3 3
7 0 8
7 6 2

Output:

9

One of the most optimal way to earn the most money is to deliver items 1 (D=1, M=3), 2 (D=2, M=9), 3 (D=4, M=3) and 5 (D=8, M=10) in which Rar the cat would earn $25. However, fuel would cost $16 from taking the path 0 -> 4 -> 1 -> 8 -> 1 -> 4 -> 2 -> 4 -> 0, resulting in the net profit of $9.

delivery.pdf

Your browser does not support embedded PDF files. Please download the PDF instead.

delivery.docx

Tags

Graph Theory, TSP, Dijkstra, Raffles Cat Helping Contest 2013

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
110101s64MBMinimum
218101s64MBMinimum
319201s64MBMinimum
423101s64MBMinimum
530201s64MBMinimum
6061s64MBMinimum

Attachments

Attachment Filesize Last Updated
delivery_sample.zip1.73KB31 Jan 2013, 15:10:01

Judge Compile Command

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