Show all threads Hide all threads Show all messages Hide all messages |
Некорректное условие | Alexey Krupnitskiy | 1004. Sightseeing Trip | 22 Jul 2022 00:07 | 2 |
1. Вы пишите:найти для экскурсии кратчайший маршрут, начинающийся и заканчивающийся в одном и том же месте, т.е. количество перекрестков в маршруте должно быть N+1?. в след. абзаце: Все числа x1, …, xk должны быть различны. т.е. либо маршрут не должен заканчиваться на том же перекресте где начался либо должно быть дополнительное условие Х1=Хк. это принципиальная ошибка в условии. 2. пример который вы привели: 5 7 1 4 1 1 3 300 3 1 10 1 2 16 2 3 100 2 5 15 5 3 20 4 3 1 2 10 1 3 20 1 4 30 -1 дает результат: 1 3 5 2 No solution. а куда вы в первом тесте дели перекрестов №4? 3. Исходя из примера маршрут не должен содержать в себе все перекрестки? Ошибки очевидны. те решения, что вы приняли - частные, случайно полученные. Уточняйте условия и проверяйте свое решение. Edited by author 07.11.2014 13:33 Нужно найти минимальное кольцо графа. Но именно кольцо, то есть, охватывать не менее трёх перекрёстков. В первом тесте к 4му перекрёстку ведёт всего одна дорога, а значит, в ответ он в любом случае не попадает. |
Условие | Davydes | 1004. Sightseeing Trip | 22 Jul 2022 00:02 | 3 |
Что-то я не совсем понял условие задачи. "M двусторонних дорог" - т.е. вроде как не ор. граф. Но пример и решение говорят, о том, что скорее это все таки ор. граф. 1 3 300 3 1 10 Так есть ориентация у ребер или нету? Написано, что возможно существование дорог, т.е. тебе нужно выбрать минимальную, а осталные проигнорировать. Два перекрёстка могут соединять несколько дорог. Но граф не ориентированный. |
Very good test!!! | 10100 | 1004. Sightseeing Trip | 21 Jul 2022 23:34 | 3 |
6 6 1 2 1 1 3 1 2 3 10 4 5 2 4 6 2 6 5 2 -1 ANS: 4 5 6 I'm sorry, but it seems incorrect. You can go from 4 to 5 or from 4 to 6, but then you're locked. Please note that we have a directed graph. Why? You can move in both directions of road. |
Can I get test #1 ? | Andreas Mihaloianis | 1004. Sightseeing Trip | 28 Nov 2020 19:09 | 6 |
My algorithm passes all the tests I have designed, but still misses test 1. Can I get the input for this test ? I have the same problem: I picked up all test data in this discussion and my program seems to be perfectly answering on all this test. Here test data and my answers: Test1 (from task description): 5 7 1 4 1 1 3 300 3 1 10 1 2 16 2 3 100 2 5 15 5 3 20 4 3 1 2 10 1 3 20 1 4 30 -1 Answer is 2 1 3 5 No solution. Well, it is not exactly the same, but seems to be correct Test #2 5 6 1 5 1 3 5 100 3 4 2 2 4 1 4 5 10 1 2 1 -1 And the answer is 2 3 4 Test #3 6 7 1 2 1 2 3 1 3 2 1 2 1 1 4 5 2 5 6 2 6 4 2 -1 Answer is 4 6 5 Test #4 2 2 1 2 10 1 2 20 -1 Answer is No solution. Test #5 6 9 1 2 1 2 3 100 3 4 1 4 5 100 5 6 1 6 1 100 1 4 5 2 5 5 3 6 5 -1 Answer is 3 4 1 2 5 6 Test #6 5 0 6 1 1 2 3 -1 Answer is No solution. No solution. Test #7 4 4 1 2 10 2 3 1 3 4 1 4 1 1 -1 Answer is 1 4 3 2 And test #8 5 6 1 5 1 3 5 100 3 4 2 2 4 1 4 5 10 1 2 1 -1 Answer is 1 5 4 2 But I am still getting WA#1 Could you suggest more data or any advise? Solved the problem, it was IO issue Hi I seem to have issue with solution for the test cases you have provided. May be I'm wrong and missing something. Please help. For this test case below 5 7 1 4 1 1 3 300 3 1 10 1 2 16 2 3 100 2 5 15 5 3 20 You state the solution as 2 1 3 5. But from the input, there is no edge from 2 to 1 or 3 to 5 (or 5 to 2 required to make this a round trip). Am I reading your answers wrong? I see this issue with each of your test case. Many of the the edges in solution are not there in the input. Please explain. ~bonfire. Edited by author 22.03.2018 02:33 Test #2 answer should be 2 4 5 1 |
if you get WA at test 1 , maybe this can help you | liusiqi | 1004. Sightseeing Trip | 1 Dec 2019 22:24 | 6 |
first...you must know that there is only one test case, ans this test case contents lots of tests... second...if you used the floyed to calculate the minimum circle,you must check the path you recorded.and, yes, the order of the crossing is not important. ok,I WA on the recording of the path,because I ignored that floyed will change the mid node of my path... sorry for my english... there is one test case that may help you : 98 146 1 2 1 2 3 300 3 4 1 4 5 300 5 6 1 6 7 300 7 8 1 8 9 300 9 10 1 10 11 300 11 12 1 12 13 300 13 14 1 14 15 300 15 16 1 16 17 300 17 18 1 18 19 300 19 20 1 20 21 300 21 22 1 22 23 300 23 24 1 24 25 300 25 26 1 26 27 300 27 28 1 28 29 300 29 30 1 30 31 300 31 32 1 32 33 300 33 34 1 34 35 300 35 36 1 36 37 300 37 38 1 38 39 300 39 40 1 40 41 300 41 42 1 42 43 300 43 44 1 44 45 300 45 46 1 46 47 300 47 48 1 48 49 300 50 51 300 51 52 1 52 53 300 53 54 1 54 55 300 55 56 1 56 57 300 57 58 1 58 59 300 59 60 1 60 61 300 61 62 1 62 63 300 63 64 1 64 65 300 65 66 1 66 67 300 67 68 1 68 69 300 69 70 1 70 71 300 71 72 1 72 73 300 73 74 1 74 75 300 75 76 1 76 77 300 77 78 1 78 79 300 79 80 1 80 81 300 81 82 1 82 83 300 83 84 1 84 85 300 85 86 1 86 87 300 87 88 1 88 89 300 89 90 1 90 91 300 91 92 1 92 93 300 93 94 1 94 95 300 95 96 1 96 97 300 97 98 1 1 50 5 2 51 5 3 52 5 4 53 5 5 54 5 6 55 5 7 56 5 8 57 5 9 58 5 10 59 5 11 60 5 12 61 5 13 62 5 14 63 5 15 64 5 16 65 5 17 66 5 18 67 5 19 68 5 20 69 5 21 70 5 22 71 5 23 72 5 24 73 5 25 74 5 26 75 5 27 76 5 28 77 5 29 78 5 30 79 5 31 80 5 32 81 5 33 82 5 34 83 5 35 84 5 36 85 5 37 86 5 38 87 5 39 88 5 40 89 5 41 90 5 42 91 5 43 92 5 44 93 5 45 94 5 46 95 5 47 96 5 48 97 5 49 98 5 50 49 3 the answer is 49 50 1 2 51 52 3 4 53 54 5 6 55 56 7 8 57 58 9 10 59 60 11 12 61 62 13 14 63 64 15 16 65 66 17 18 67 68 19 20 69 70 21 22 71 72 23 24 73 74 25 26 75 76 27 28 77 78 29 30 79 80 31 32 81 82 33 34 83 84 35 36 85 86 37 38 87 88 39 40 89 90 41 42 91 92 43 44 93 94 45 46 95 96 47 48 97 98 Hello! I pass your test data but I still get WA,why? Is there any other trick? Sorry for my poor english too. :) Oh,I get AC! Beacuse my inf is too large. It should be small than INT_MAX/3. So somebody else who get WA should notice it. More test data: 5 0 6 1 1 2 3 -1 Edited by author 02.08.2011 08:24 Edited by author 02.08.2011 08:25 my answer is 1 2 51 52 3 4 53 54 5 6 55 56 7 8 57 58 9 10 59 60 11 12 61 62 13 14 63 64 15 16 65 66 17 18 67 68 19 20 69 70 21 22 71 72 23 24 73 74 25 26 75 76 27 28 77 78 29 30 79 80 31 32 81 82 33 34 83 84 35 36 85 86 37 38 87 88 39 40 89 90 41 42 91 92 43 44 93 94 45 46 95 96 47 48 97 98 49 50 but it is stall WA in test one! who can give more test cases? 6 9 1 2 1 2 3 100 3 4 1 4 5 100 5 6 1 6 1 100 1 4 5 2 5 5 3 6 5 1 2 5 6 3 4 Edited by author 20.04.2013 19:32 Thanks, you are true hero! |
to admin: about multi-edge | Ade | 1004. Sightseeing Trip | 25 Apr 2017 08:30 | 3 |
My AC code: input: > 3 3 > 1 2 1 > 1 2 1 > 1 3 1 > -1 output: > No solution. Why not > 1 2 There are two roads connecting "1" and "2", so the route could be 1 - 2 - 1, with different road 1 - 2 and 2 -1 "Each sightseeing route is a sequence of road numbers y1, …, yk, k > 2." Oops. Sorry for bothering! "Each sightseeing route is a sequence of road numbers y1, …, yk, k > 2." |
What to do with multiple roads? | Ade | 1004. Sightseeing Trip | 21 Apr 2017 20:47 | 2 |
What's should the following input get? 3 4 1 2 1 2 3 1 1 3 1 1 2 1 3 4 1 2 1 2 3 1 1 3 1 1 2 10 -1 Thanks! got it. My AC code gives 1 2 3 1 2 3 |
if you have WA3 | MrBones | 1004. Sightseeing Trip | 25 Jan 2017 04:16 | 1 |
Try this test: 6 6 1 2 1 2 3 100 3 1 99 4 5 150 5 6 1 6 4 1 -1 Answer: 4 5 6 |
Golang 1.3: Extremely Slow fmt.Scanf | Linh Tran Tuan | 1004. Sightseeing Trip | 20 May 2016 21:26 | 1 |
!!Please be aware of fmt.Scanf poor performance!! I did everything to test it on Timus and feel so sorry for it. My code logic is ok except this! It took a day to figure out. I got AC with FreePascal before, and now Golang. So my advice is: read all input first using bufio and ioutil like this: input = bufio.NewReader(os.Stdin) output = bufio.NewWriter(os.Stdout) _wholeText, _ := ioutil.ReadAll(input) numbers := strings.Fields(string(_wholeText)) |
A got AC,but my algo is O(N^3). I know algo O(N*N*logN). | Felix_Mate | 1004. Sightseeing Trip | 6 Sep 2015 15:49 | 1 |
Idea is Dijkstra (N times from every node). I can proof that minimal cycle turns when we add one edge in root tree (tree of distance). Edited by author 06.09.2015 15:53 Edited by author 06.09.2015 15:54 |
TLE #3 | [FALL] Levon Oganesyan [RAU] | 1004. Sightseeing Trip | 23 Aug 2015 18:40 | 2 |
TLE #3 [FALL] Levon Oganesyan [RAU] 21 Mar 2015 01:19 I use the algo with N Dijkstras. Does anyone know, can I get AC with that algo, or 0.5 sec is not enough for it? I use Dijkstra and the language Python. If you are using C/C++ you can be well within the 0.5 sec, when implemented properly. |
WA 2 | Axis | 1004. Sightseeing Trip | 19 Aug 2015 02:18 | 2 |
WA 2 Axis 19 Jan 2015 21:32 Hello. Do not pass the test number two. Tested the algorithm all the data found on the Internet, all the tests pass. What is important is whether the value of the order of numbers in the answer? Whether equivalent variants "1 2 3 4" and "3 4 1 2"? Perhaps you can give a piece of advice. Be careful about multiple edges It causes bugs in your dijkstra alg... Edited by author 19.08.2015 02:19 |
Ошибка в условии? Лучший путь для Теста 1 = 1->4->1 | zzox3 | 1004. Sightseeing Trip | 9 Dec 2014 01:06 | 6 |
Условия: > найти для экскурсии кратчайший маршрут, начинающийся и заканчивающийся в одном и том же месте. > Ваша программа должна найти маршрут наименьшей длины > и M двусторонних дорог, В ТЗ не сказано что нужно обойти максимум перекрестков, не сказано что нельзя ехать назад. А значит путь: 1 -> 4 -> 1 подходит. В условии сказано "Все числа x1, …, xk должны быть различны.". я пол дня пытаюсь сдать задачу. в НЕТБИНС работают все примеры у вас постоянно РАНТАЙМ ЕРОР. начинаю сомневаться в корректности вашей проверки. и второе - задача некорректна. пишите что маршрут должен начинаться и кончаться в одном месте а в след. абзаце пишите что все Хк должны быть различны. вы уж определитесь. А вы не пробовали прочитать: 1) условие 2) формат вывода 3) пример ??? Из первого ясно, что маршрут должен состоять как минимум из трех РАЗЛИЧНЫХ вершин, последние два поясняют. > В условии сказано "Все числа x1, …, xk должны быть различны.". Ну дак в "1 4" нет повторения перекрестков. Про повторение дорог ничего не сказано. There is state that k > 2. In your example k == 2. |
How to deal with this problem? | pyh119 | 1004. Sightseeing Trip | 27 Nov 2014 11:43 | 7 |
I can not solve it,please tell me how to solve it,thank you!^_^ You can do this for all edges: 1 - delete edge 2 - find shortest way (Deikstra) between 2 vertex, which are connetcted with this edge 3 - insert edge This solution (O(N^4))pass time limits P.S. It may done in N^3 with Deikstra for each vertex I don't know how to do this :( Is there anything to do with Hamiltonian circuit ? Hamiltonian circuit for n=100 ?!?!?! We will die before your program will give us an answer :O Well... it's not always true that Hamiltonian related problems are NP completed. You can always use some heuristics that will reduce it to polynomial time... so don't be so marked ^^ |
Still could be solved by O(n^4) algorithm | Alexander Kouprin | 1004. Sightseeing Trip | 24 Nov 2014 00:14 | 2 |
0.343 sec. Just to let you know. ;) Heh, 0.35 sec... Mine is O(N^4) and 0.078 |
Why Crash(Access Violation) at #1? | wuyihao | 1004. Sightseeing Trip | 7 Nov 2014 14:24 | 2 |
I tested it offline,and I got WA 90. But when I submited it.I got Crash(Access Violation). There's another question. For this input: 98 146 1 2 1 2 3 300 3 4 1 4 5 300 5 6 1 6 7 300 7 8 1 8 9 300 9 10 1 10 11 300 11 12 1 12 13 300 13 14 1 14 15 300 15 16 1 16 17 300 17 18 1 18 19 300 19 20 1 20 21 300 21 22 1 22 23 300 23 24 1 24 25 300 25 26 1 26 27 300 27 28 1 28 29 300 29 30 1 30 31 300 31 32 1 32 33 300 33 34 1 34 35 300 35 36 1 36 37 300 37 38 1 38 39 300 39 40 1 40 41 300 41 42 1 42 43 300 43 44 1 44 45 300 45 46 1 46 47 300 47 48 1 48 49 300 50 51 300 51 52 1 52 53 300 53 54 1 54 55 300 55 56 1 56 57 300 57 58 1 58 59 300 59 60 1 60 61 300 61 62 1 62 63 300 63 64 1 64 65 300 65 66 1 66 67 300 67 68 1 68 69 300 69 70 1 70 71 300 71 72 1 72 73 300 73 74 1 74 75 300 75 76 1 76 77 300 77 78 1 78 79 300 79 80 1 80 81 300 81 82 1 82 83 300 83 84 1 84 85 300 85 86 1 86 87 300 87 88 1 88 89 300 89 90 1 90 91 300 91 92 1 92 93 300 93 94 1 94 95 300 95 96 1 96 97 300 97 98 1 1 50 5 2 51 5 3 52 5 4 53 5 5 54 5 6 55 5 7 56 5 8 57 5 9 58 5 10 59 5 11 60 5 12 61 5 13 62 5 14 63 5 15 64 5 16 65 5 17 66 5 18 67 5 19 68 5 20 69 5 21 70 5 22 71 5 23 72 5 24 73 5 25 74 5 26 75 5 27 76 5 28 77 5 29 78 5 30 79 5 31 80 5 32 81 5 33 82 5 34 83 5 35 84 5 36 85 5 37 86 5 38 87 5 39 88 5 40 89 5 41 90 5 42 91 5 43 92 5 44 93 5 45 94 5 46 95 5 47 96 5 48 97 5 49 98 5 50 49 3 -1 My answer is:49 98 97 And I think it was quit correct. But the output is: 49 50 1 2 51 52 3 4 53 54 5 6 55 56 7 8 57 58 9 10 59 60 11 12 61 62 13 14 63 64 15 16 65 66 17 18 67 68 19 20 69 70 21 22 71 72 23 24 73 74 25 26 75 76 27 28 77 78 29 30 79 80 31 32 81 82 33 34 83 84 35 36 85 86 37 38 87 88 39 40 89 90 41 42 91 92 43 44 93 94 45 46 95 96 47 48 97 98 Can anybody tell me how to solve these questions. Thank you very much |
use Floyd-Warshall algorithm | idiot123 | 1004. Sightseeing Trip | 18 Sep 2014 13:08 | 1 |
I read this algorithm in INTRODUCTION OF ALGORITHM at chapter 25.If you had already read this algorithm,you can easily solve this problem. |
To admins: please add this test | MVM | 1004. Sightseeing Trip | 30 Jul 2014 03:31 | 1 |
Please add this test (if it is not already here and if it is not too hard): 100 133 1 2 1 1 34 300 2 3 1 3 4 1 4 5 1 5 6 1 6 7 1 7 8 1 8 9 1 9 10 1 10 11 1 11 12 1 12 13 1 13 14 1 14 15 1 15 16 1 16 17 1 17 18 1 18 19 1 19 20 1 20 21 1 21 22 1 22 23 1 23 24 1 24 25 1 25 26 1 26 27 1 27 28 1 28 29 1 29 30 1 30 31 1 31 32 1 32 33 1 33 34 1 34 36 300 34 35 1 35 36 1 36 37 1 36 38 150 37 38 1 38 39 1 38 40 75 39 40 1 40 41 1 40 42 38 41 42 1 42 43 1 42 44 19 43 44 1 44 45 1 44 46 10 45 46 1 46 48 5 46 47 1 47 48 1 48 50 3 48 49 1 49 50 1 50 52 2 50 51 1 51 52 1 52 54 1 52 53 1 53 54 1 54 55 1 54 56 1 55 56 1 56 57 1 56 58 1 57 58 1 58 60 1 58 59 1 59 60 1 60 62 1 60 61 1 61 62 1 62 64 1 62 63 1 63 64 1 64 65 1 64 66 1 65 66 1 66 67 1 66 68 1 67 68 1 68 70 1 68 69 1 69 70 1 70 72 1 70 71 1 71 72 1 72 74 1 72 73 1 73 74 1 74 76 1 74 75 1 75 76 1 76 77 1 76 78 1 77 78 1 78 79 1 78 80 1 79 80 1 80 82 1 80 81 1 81 82 1 82 84 1 82 83 1 83 84 1 84 86 1 84 85 1 85 86 1 86 87 1 86 88 1 87 88 1 88 89 1 88 90 1 89 90 1 90 91 1 90 92 1 91 92 1 92 93 1 92 94 1 93 94 1 94 96 1 94 95 1 95 96 1 96 98 1 96 97 1 97 98 1 98 99 1 98 100 300 99 100 1 repeated 5 times. One of my AC submissions works 0.8 seconds locally on this test, but works 0.187 seconds max on judge. Even though my computer is slower than judge, it still looks like a big difference. |
Did anyone get AC with O(n4) algo after redjudgement 15 Sep 2013 | sanok | 1004. Sightseeing Trip | 16 Jun 2014 14:10 | 1 |
I implemented the first idea came to my mind: for each connected vertices v1,v2 removing edge v1-v2 and finding shortest paths from v1 to v2 with Dijkstra. As for my estimations it should be O(edges^2) or O(vertices^4) for very connected graphs. It was reported in other threads of this discussion that this solution should fit time limits, but mine does not pass test #3 (time limit exceed). I am curious if solutions like mine now can be accepted. Did anyone have success with that approach after rejudgement in Sep 2013? Or now only O(v^3) solutions can pass all tests? Thanks |
I've got TL#1.Is the Test#1 so difficult? | cpc | 1004. Sightseeing Trip | 17 Mar 2014 04:59 | 15 |
I have the same problem and I don't know why. If somebody know this test or some other like that, please show it. I supose that there is only one test... But all what you need is delete one road between 2 points and with help of Deikstra find out the shortest way between this points ... than add length of road and you find out the shortest way throw this row.... and so on! I solved this problem such way! It's O(N^4)! You can optimize this nice idea to reach O(N^3)! here is test 1: 4 6 1 2 40 1 3 50 1 40 60 2 3 10 2 4 30 3 4 20 one answer: 2 3 4 Edited by author 21.10.2005 16:50 Thanks for your test... :) I have AC 0.046 sec... but this problem says: "...In the town there are N crossing points numbered from 1 to N..." here is test 1: 4 6 1 2 40 1 3 50 1 40 60 2 3 10 2 4 30 3 4 20 one answer: 2 3 4 My program prints: 2 4 3 It's true, imho. I think It's : 1 2 40 1 3 50 1 4 60 2 3 10 2 4 30 3 4 20 my ans is 2 3 4,but get WA at Test#1 Impossible. I get 2 3 4 as answer at get wrong answer on #1 Floyd Algrathm is also advisable. However, please take note of another test: 4 4 1 2 10 2 3 1 3 4 1 4 1 1 should output things like 1 4 3 2 but NOT 1 4 3 4 |