Блог пользователя ldn694

Автор ldn694, история, 4 года назад, По-английски

Hello Codeforces. I have just recently joined a contest at my school. In that contest, there was a problem requiring counting the number of shortest paths from a vertex s to every other vertex in a directed weighted graph. I have implemented my idea and tested it a bit so I had a strong belief that my code was correct. In the end, it turned out that the code was wrong. The contest gave me only one submission for each problem so I didn't have a chance to fix it during the contest. I have tried to find my mistakes in the code at home but I found nothing. Here is the code similar to what I submitted during the contest.

The code

Can anyone help me point out the mistake in the algorithm or maybe this was not the incorrect part in my initial code? I would be so grateful if you can provide a link to another problem that also requires counting the number of shortest paths so that I can test the code by myself. Thanks for reading and have a good day.

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by ldn694 (previous revision, new revision, compare).

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by ldn694 (previous revision, new revision, compare).

»
4 года назад, # |
  Проголосовать: нравится +57 Проголосовать: не нравится

Have you tried the following:

  • Write a very naive and simple solution to the problem (maybe exponential complexity) (if you can, you may also just copy someone else's solution)
  • Write a program to generate thousands of small (!) test cases
  • Using those two, find a test case where your program gives the wrong answer
  • Use print statements or a debugger to see where exactly your program does the wrong thing.

98% of WAs and REs can be resolved this way. People here don't have the time to delve into every code posted here, it's much harder to debug somebody else's code and being able to debug your own code is a valuable skill. It is also a very routine process that can be learned much faster than problem solving and algorithms.