LKP '18 Contest 1 P4 - Fun in Föràg - DMOJ: Modern Online Judge

LKP '18 Contest 1 P4 - Fun in Föràg

View as PDF

Submit solution

All submissions

Best submissions

Points: 15 (partial)

Time limit: 1.0s

Java 1.8s

Memory limit: 64M

Authors:

george_chen, KevinWan

Problem type

The transport system of the city of Föràg consists of $N$ ~N~ stations and $M$ ~M~ two-way trains connecting the stations, the $i$ ~i~th of which takes $c_i$ ~c_i~ minutes go from station $a_i$ ~a_i~ to station $b_i$ ~b_i~ or from station $b_i$ ~b_i~ to station $a_i$ ~a_i~. Konajya is currently near station $A$ ~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$ ~B~ in $C$ ~C~ minutes. To use the Föràgian transport system, Konajya must first buy a transport pass. There are $M$ ~M~ levels of passes, the $i$ ~i~th of which gives access to the first $i$ ~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)

Constraints

In all subtasks,
$1 \le N \le 100\,000$ ~1 \le N \le 100\,000~
$1 \le M \le 200\,000$ ~1 \le M \le 200\,000~
$1 \le a_i,b_i,A,B \le N$ ~1 \le a_i,b_i,A,B \le N~
$1 \le c_i \le 10^6$ ~1 \le c_i \le 10^6~
$1 \le C \le 10^{11}$ ~1 \le C \le 10^{11}~

Subtask 1 [15%]

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

Subtask 2 [85%]

No additional constraints.

Input Specification

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

Output Specification

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

Sample Input

Sample Output

Comments

0

pblpbl commented on Jan. 26, 2020, 2:48 p.m. ← edited →

I was looking at this problem and https://dmoj.ca/problem/ccc15s4 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?

0
max commented on Jan. 24, 2020, 5: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?

2

Dingledooper commented on Jan. 25, 2020, 2:03 a.m. ← edit 3 →

Adding if (d > dist[at]) continue; right after popping your queue solves the problem. Without it the worst case runs in $\mathcal{O}(NM)$ ~\mathcal{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".

0

devnarula commented on June 28, 2020, 3:40 p.m.

so is it equivalent to keeping a visited array?

1

max commented on Jan. 25, 2020, 2:49 a.m.

AC! Thank you.