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

dinowalk Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

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

dinowalk.html

Problem Statement

Rar the Cat is helping to build a road network so that humans can walk with dinosaurs.

There are a total of N cities and Rar the Cat has already build several roads between them. However, dinosaurs vary in height and each road has its own height limit.

A road network is considered 'safe for X m' if a dinosaur (or human or cat) can travel between any two pairs of cities without exceeding the height limits of any road in its path.

Rar the Cat wants to calculate what is the largest possible X value so he knows whether Jacq the tall T-Rex can travel safely on his road network.

Input

The first line of input will be N, the number of cities. There will not be more than 500 cities.

Subsequent N lines will contain N integers each. The jth integer of the ith row is the height limit for the road that allows dinosaurs to travel from city i to city j.

Do note that the height limits are not the same for both directions. Furthermore, some roads might be only 1-way. If the height limit is 0, it means that there is no road. It is guaranteed that there is no road from city i to city i itself.

All height limits are in metres and will not exceed 1000km

Output

The first line of output should contain only one integer, the maximum value of X such that the road network is safe for dinosaurs of Xm

If there is no indirect or direct path between any two cities within the road network, output 0 instead.

Subtasks

This problem employs an average grading scheme and has no subtasks.

Sample Input

5
0 1 2 3 4
2 0 1 3 2
5 2 0 1 3
1 1 4 0 1
1 2 3 4 0

Sample Output

2

Explanation for Sample Output

Although the direct road from city 1 to city 2 has a height limit of only 1, a dinosaur can first go to city 3 along the road with height limit 2 and then go back to city 2 along the road with height limit 2.

Therefore, the road network is also considered safe for dinosaurs ≤ 2m high

img8987.jpg

Tags

Graph Theory, Floyd Warshall

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
1100501s32MBAverage
2011s32MBMinimum

Judge Compile Command

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