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

wormholes Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

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

wormholes.html

Problem Description

You are an inter-galactic traveller in a 1-dimensional space. There are n planets in total, numbered 0 to n-1, all lined up in sequence with each of them a fixed distance apart. The time taken to travel from each planet to the next is 1 light year. For instance, travelling from planet 0 to planet 9 would normally take 9 light years.

However, there are also a number of wormholes that exist that whisk a traveller from planet x to planet y in 1 light year, regardless of how far apart x and y really are. Note that y is always greater than x. In other words, all wormholes will take you further away from planet 1.

Now, your task is to figure out the shortest time you can take to travel from planet 0 to planet n-1, using the optimal selection of wormholes. You do not need to print out the path you will take, but only the amount of time this path will take, in light years.

The first line of input will give you the number of planets (n), the second line will give you the number of wormholes that exist, and the subsequent lines will give you the pairs of planets that the wormholes can take you from and to. Your output will be a single number (with a newline at the end) indicating the shortest number of light years it will take for you to travel from planet 0 to planet n-1. n will be at most 255.

The number of wormholes will be at most 255 as well.

Sample Input 1

10
2
3 5
7 9

Sample Output 1

7

Sample Input 2

10
2
1 3
2 7

Sample Output 2

5

Tags

Dynamic Programming

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
110051s32MBAverage
2021s32MBAverage

Judge Compile Command

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