SyFy's blog

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

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

  • »
    »
    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 ?
    • »
      »
      »
      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.

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