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

Can somebody help me to find out why this code gets WA?
Автор SyFy, 13 лет назад, По-английски

Problem 144D Codeforces Round #103 (Div. 2)


Here is my submission.

Rewrote Dijkstra already 3-4 times (not enough?)... but I think I am doing something wrong with SortedList.

Thx.
  • Проголосовать: нравится
  • -2
  • Проголосовать: не нравится

»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
You store vertices in a sortedlist with distance key. What if there are more then one vertex for some distance and program removes wrong pair (it compare pairs ONLY by key)?
→ Ответить
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Nope, the key is pair<int, int>, where first value is the distance and the second - vertex id.
    Third value I dont need, so I just set it to zero.
    → Ответить
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      TL 22

      Your comparer checks distance, not the vertex. For example, pairs (fst=1,snd=5) and (fst=1,snd=6) are equal. SortedList uses comparer and removes first element with same "fst" value.
      I fixed it and got TL 22.
      → Ответить
»
13 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

I am from Java ,so dont know much about the c#.However I think there is a problem in your implemtation in Dijkstra.
When I swapped :

sl.Remove (new pair (dist [p.fst], p.snd));

with

dist [p.fst] = weight + p.snd;

It passed the 10th test case but failed on the 12th.Here's my submission.__

→ Ответить
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
TL 22
Comparer checks distance, not the vertex. For example, pairs (fst=1,snd=5) and (fst=1,snd=6) are equal. SortedList uses comparer and removes first element with same "fst" value.
I fixed it and got TL 22.

→ Ответить
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Thx!
    Interesting test 22:
    Test: #22, time: 2000 ms., memory: 18368 KB, exit code: 0, checker exit code: 0, verdict: TIME_LIMIT_EXCEEDED
    Input
    40000 60000 3782
2 1 399
3 1 321
4 1 320
5 4 236
6 4 295
7 2 892
8 1 277
9 3 761
10 4 1000
11 4 453
12 7 455
13 9 283
14 10 402
15 4 171
16 6 420
17 4 626
18 14 627
19 12 876
20 7 124
21 5 788
22 7 793
23 6 616
24 8 788
25 1 967
2...
    Output
    5621
    Answer
    Checker Log

    why we have TLE with not empty Output ?
    → Ответить
»
13 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

I think maybe SPFA is a good way to solve this problem.

→ Ответить