i_love_sharapova's blog

ATCODER BEGINNER CONTEST 061
By i_love_sharapova, history, 4 years ago, In English

i was solving problem D-SCORE ATTACK of ABC 061 and i tried implementing classic bellman ford algorithm by changing the weight to -ve weight ,so as if any negative cycle occurs then that means score will be continuously increasing but i am getting WA ,i don't know where i am making mistake and i have assumed that graph is connected so either my assumption is wrong or i am implementing wrong algorithm .please can you guys help ? sorry if my english is bad.

here is my code
  • Vote: I like it
  • 0
  • Vote: I do not like it

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

You could have a negative cycle, which isn't on the main path.

N = 5
1 5 2
1 2 5
2 3 -1
3 2 -1
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    so does it mean that we can't have any negative cycle on any vertex except at N.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You can't have a cycle on any path between 1 and N, as that will become the shortest path.

      → Reply