SyFy's blog

Can somebody help me to find out why this code gets WA?
By SyFy, 13 years ago, In English

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.
  • Vote: I like it
  • -2
  • Vote: I do not like it

»
13 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.__

→ Reply
»
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
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.

→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    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 ?
    → Reply
    • »
      »
      »
      13 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      your program needs to clear memory before exit, and this process is very slow, i think.

      → Reply
»
13 years ago, # |
  Vote: I like it -8 Vote: I do not like it

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

→ Reply