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

car Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

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

car.html

Problem Description

There are N cities labelled from 1 to N connected with E roads and Rar the Cat wants to travel from city 1 to city N. Each road has a particular distance and Rar the Cat is intending to buy a car to travel the distance between the cities. The cars have a specific mileage (Eg. Can only travel up to 100 kilometers) and therefore can only travel between cities where the road between them if their roads is less than or equal to 100 kilometers long (Rar the Cat can refuel at each city).

Rar the Cat wants to know the minimum mileage the car should have in order to travel from city 1 to city N as a car with a lower mileage costs less! Do note that Rar the Cat do not need to travel the minimum distance from city 1 to city N.

Input

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

The subsequent E lines of input consists of 3 integers each A, B and D. This means that there exist a bi-directional road from A to B with distance of D kilometers. A and B would be a valid city (from 1 to N) and D will fit into a 32-bit signed integer.

The input will not contain 2 roads between any pair of 2 cities and all cities are connected to one another via one way or another.

Output

A single integer, the mimimum mileage the car should have in kilometers.

Limits

Subtask 1 (25%): 0 < N, E ≤ 100

Subtask 2 (25%): 0 < N, E ≤ 1000

Subtask 3 (50%): 0 < N, E ≤ 1000000

Sample Testcase

Input:

5 7
1 2 10
1 5 10
2 3 10
3 4 2
4 5 10
1 4 1
3 5 1
Output:
2
Explanation:
The minimum mileage is 2km as Rar the Cat can travel from 1 to 4 (1km), 4 to 3 (2km) and then 3 to 5 (1km). This is the minimum mileage required.

Tags

Minimum Spanning Tree, Union Find Disjoint Set, Graph Theory

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
125301s64MBMinimum
225301s64MBMinimum
350301.5s64MBMinimum
4011s64MBMinimum

Judge Compile Command

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