| Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
| wa17 | 👑TIMOFEY👑 | 1905. Путешествия во времени | 6 июл 2023 12:28 | 1 |
wa17 👑TIMOFEY👑 6 июл 2023 12:28 u visit end vertex more than one time, idk why we need only 1 time it visit, but by that i got ac |
| WA4 or WA6 | andreyDagger`~ | 1905. Путешествия во времени | 13 ноя 2022 02:57 | 1 |
1 12
1 1 10 8
1 1 8 10
1 1 9 3
1 1 7 4
1 1 2 4
1 1 5 4
1 1 2 5
1 1 9 9
1 1 3 5
1 1 9 2
1 1 9 5
1 1 5 9
1 1 6 4
Ans:
1
4
Also, check that you print "Impossilbe", when it's impossible to achieve the finish vertex |
| solution | Berezhko German | 1905. Путешествия во времени | 7 окт 2022 10:48 | 3 |
solution Berezhko German 14 окт 2012 12:52 dfs or bfs is the correct idea?
oh, i'm done with it (:
Edited by author 15.10.2012 15:14
Edited by author 15.10.2012 15:22
Edited by author 14.10.2012 16:49 Yes, it's BFS with plenty of binary searches to build initial graph. |
| wa 12 | Abid29 | 1905. Путешествия во времени | 28 апр 2021 17:08 | 1 |
wa 12 Abid29 28 апр 2021 17:08 try this one
2 2
1 1 3 2
1 2 3 3
1 2 2 4
1
2 |
| some tests | Felix_Mate | 1905. Путешествия во времени | 7 авг 2017 20:56 | 1 |
1)
4 4
1 2 9 15
1 4 0 8
2 3 20 30
3 1 31 0
1 4 9 30
->
4
1 3 4 2
2)
2 3
1 2 0 5
1 1 110 80
1 1 90 0
1 2 100 6
->
3
2 3 1
3)
3 6
1 2 50 55
2 1 55 40
1 2 0 1
1 3 41 80
3 2 80 12
2 1 15 0
1 2 49 7
->
6
1 2 4 5 6 3 |
| WA 4 | Vladimir Leskov [USU] | 1905. Путешествия во времени | 24 авг 2015 13:29 | 1 |
WA 4 Vladimir Leskov [USU] 24 авг 2015 13:29 For those, who has WA4, try this test:
Input:
1 0
1 1 10 20
Output:
0 |
| Problem 1905. Travel in Time rejudged | Vladimir Yakovlev (USU) | 1905. Путешествия во времени | 15 апр 2015 09:49 | 1 |
New tests have been added, 24 authors have lost AC. |
| Test 13 | RR | 1905. Путешествия во времени | 8 май 2013 16:26 | 2 |
Hi,
At first my program finds the flights that lead to smallest time, and get WA13. Then I modified one line:
trace(target, bestTime);
to
trace(target, timeInInput);
and got accepted.
I already added edges from (u,t) --> (u,t') for t' > t, so that if my bfs finds a path to (u,t), it should also find a path to (u,t') for all t' >= t.
So I think either judge is incorrect, or test data is weak (such that my wrong code got accepted). Hi,
I encountered the same result (WA @ 13) as you did, and after a second thought, I realized that we had misunderstood the problem statement, in which an important sentence shall be noted:
"Since such a meeting would likely be fatal, it cannot be allowed until the job is done."
Remember that you need to wait for the rebel leader to appear at TIME_IN_INPUT. Therefore, if you take another round-trip to arrive at sometime earlier than first arrival, you would definitely meet yourself, which would be fatal. That's why we need to terminate the program once we arrive at the destination earlier than TIME_IN_INPUT.
BTW, it SEEMS that terminating the BFS process in such a way would lead to the smallest k. |
| WA 25 | YerzhanU | 1905. Путешествия во времени | 26 янв 2013 02:38 | 3 |
WA 25 YerzhanU 14 окт 2012 00:30 Shoud we minimize k ? I got accepted when I minimized k.
Edited by author 14.10.2012 11:07 Seconded. I did not see anywhere to minimise k, and my dfs did not pass but my bfs did. Maybe I screwed up the implementation... Shoud we minimize k ? I got accepted when I minimized k.
I used dfs, and got accepted. So I don't think it is necessary to minimize k. |
