All Tracks Algorithms Graphs Shortest Path Algorithms Problem

Lost in a city

Algorithms, Dijkstra, Easy-Medium, Graphs, Shortest Path Algorithms


A country consists of \(n\) cities and \(m\) one-way roads. There is a central city with number \(s \). Each city sells a particular sweet (city \(i\) sells sweets of value \(v[i]\)).

You are required to go to city \(d\). If you are currently in city \(x\), then you can randomly select and move to one of the cities that is directly reachable from \(x\) through a single road. You can perform this technique until you reach city \(d\). You must stop once you reach the destination city. 

You can buy sweets only once on your way. Determine the highest value \(p\) such that you can take home a sweet whose value is at least \(p\) independent of the path that you take. Print the value of \(p\) for each destination city \(d\) from \(1\) to \(n\)


  • It is guaranteed that all the cities are reachable from the central city.
  • You can not select a road that does not lead to the destination.
  • There are multiple test cases in a single input file.

Input format

  • First line: An integer \(t\) denoting the number of test cases 
  • For each test case:
    • First line: Three integers \(n\)\(m\), and \(s\)
    • Next line: \(n\) integers denoting the value of a sweet that is sold in each city 
    • Next \(m\) lines: Two integers \(u\) and \(v\) denoting a directed road from city \(u\) to \(v\)

Output format

For each test case, print \(n\) space-separated integers denoting the answer to each destination city.


\(1 \leq t \leq 3\)

\(1\le n,u,v,s\le10^5\)

\(1\le m\le2*10^5\)

\(1\le v[i]\le10^6\)

3 4 1
3 4 5
1 2
1 3
2 3
3 2
4 5 2
6 3 2 5
2 1
2 4
1 3
4 3
3 1
3 4 5 
6 3 5 5 

In the second testcase:

There is only one path for reaching city 1, and he will buy sweets of value 6 in city 1. There is also only one path for reaching city 4 and he will buy sweets of value 5 from city 4. There are two paths 2->4->3 and 2->1->3 for reaching city 3. In the first path he can buy sweets of value 5 from city 4 and in the second path he can buy sweets of value 6 from city 1. So he can take sweets of value at least 5 if the destination city is 3. 

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic


Initializing Code Editor...
Your Rating:


This Problem was Asked in


Challenge Name

July Circuits '19

View All Notifications