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

goinghome_ex Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

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

goinghome_ex.html

Problem Description

Samuel lives in a one-dimensional world. RI is at the leftmost point in this one-dimensional world. After programming training, Samuel is heading home from school. His house is located N kilometers away. In this one-dimensional world, there are bus stops that are spaced 1 kilometer apart. S shuttle buses run from one bus stop to another, but only travel in the right direction.

Each shuttle bus costs a certain amount of money to ride. Alternatively, Samuel can also take a taxi between certain bus stops, which charge a flat rate of R dollars per kilometer. Given the list of shuttle buses and their respective sources, destinations and cost, output the least amount of money in dollars Samuel can use to reach home.

Input

The first line of input will contain three integers, N, S and R.
The next S lines of input will contain three integers each, the source, the destination and the cost of the shuttle i.

Output

Your output should contain one integer, the least amount of money in dollars Samuel can use to reach home.

Limits

Subtask 1: 1 ≤ N, S ≤ 1000000 (30%)
Subtask 2: 1 ≤ S ≤ 1000000, N will fit into a 32-bit signed integer. (70%)
Subtask 3: As per sample testcases

Sample Input 1

5 3 3
0 4 6
3 5 3
4 5 2

Sample Output 1

8

Tags

Dynamic Programming

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
130520s512MBMinimum
270520s512MBMinimum
30120s512MBMinimum

Judge Compile Command

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