Fun in Föràg

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 1.0s
Java 1.8s
Memory limit: 64M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

The transport system of the city of Föràg consists of N stations and M two-way trains connecting the stations, the ith of which takes c_i minutes go from station a_i to station b_i or from station b_i to station a_i. Konajya is currently near station A after visiting the Föràgian War Museum. However, she wants to go visit the Lastrevia cultural festival which is conveniently going to be held directly beside station B in C minutes. To use the Föràgian transport system, Konajya must first buy a transport pass. There are M levels of passes, the ith of which gives access to the first i trains in the order given in the input statement. Help Konajya find the minimum level of the transport pass that she must buy to reach the cultural festival before it starts! (You may assume the time needed to get to the station and to buy the pass is negligible)


In all subtasks,
1\le N\le100\,000
1\le M\le200\,000
1\le a_i,b_i,A,B\le N
1\le c_i\le10^6
1\le C\le 10^{11}

Subtask 1 [15%]

1 \le N, M \le 2\,000

Subtask 2 [85%]

No additional constraints.

Input Specifications

The first line contains two integers, N and M.
M lines will follow. The ith of these will contain the integers a_i, b_i and c_i.
The last line will contain three more integers, A, B, and C.

Output Specifications

Output the minimum level of the Föràgian transport pass that Konajya must get so that she can get from station A to station B in less than C minutes. If this is not possible print -1 instead.

Sample Input

4 4
1 4 10
1 2 3
3 4 2
2 3 1
1 4 9

Sample Output



  • 1
    pblpbl  commented on Jan. 26, 2020, 9:48 a.m. edited

    I was looking at this problem and and I realized that they were quite similar. However, after implementing a similar solution I couldn't entirely get the full solution on the other problem. Therefore I think my solution may have had flaws that were not picked up by the test cases. Can anyone check my code and figure out if I have the correct solution or just one that managed to pass all of this problem's test cases?

  • 2
    Dingledooper  commented on Jan. 24, 2020, 9:03 p.m. edit 2

    @max Adding if (d > dist[at]) continue; right after popping your queue solves the problem. Without it the worst case runs in O(NM). Why? Because in Dijkstra's algorithm a vertex can have multiple weights in the queue, so to work around it we only proceed if the node is not "old". (also apparently i don't know how to reply to a comment)

    • 0
      devnarula  commented on June 28, 2020, 11:40 a.m.

      so is it equivalent to keeping a visited array?

    • 2
      max  commented on Jan. 24, 2020, 9:49 p.m.

      AC! Thank you.

  • 0
    max  commented on Jan. 24, 2020, 12:18 a.m.

    I am fairly certain that I have implemented the intended solution to this question, however my programme is unable to make it past case #72 of the second batch due to a TLE verdict.

    I am using optimised streams for I/O; and have declared all arrays globally as recommended on the tips page.

    Additionally, I have tried:

    • Pragmas
    • __attribute__ ((hot)) before the definition of my main routine

    Are there any more optimisations I can make in order for my programme to be accepted?