Tariqul's blog

Codeforces Beta Round #25 (Div. 2 Only) Problem C Roads in Berland
By Tariqul, 14 years ago, In English

In the problem statement it is said that length of roads will be maximum 1000.

But in Test case 4 and more other test case it was given more than 1000.
Can anyone clarify me whether I have wrong understanding or not.

Thanks.
  • Vote: I like it
  • -11
  • Vote: I do not like it

14 years ago, # |
← Rev. 2   Vote: I like it +16 Vote: I do not like it

in case4 the distance between the two cities more than 1000, not the length of road.
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Thanks a lot.
    But where problem said the distance limit between two cities that can be more than 1000.

    → Reply
    • 14 years ago, # ^ |
      ← Rev. 3   Vote: I like it +1 Vote: I do not like it

      Nope.
      "Each road has its own length — an integer number from 1 to 1000."
      Sometimes you need to use more than one road to get from one town to another, so the shortest distance could be larger that 1000.

      Also:
      "Then there follow n lines with n integer numbers each — the matrix of shortest distances"

      Test 4:
      4
0 537 1064 656
537 0 527 119
1064 527 0 408
656 119 408 0
4
1 4 123
1 4 344
3 2 982
3 2 587
      The length of planned roads cannot be larger than 1000, but the shortest distance using existing roads can be larger.

      P.S. Sorry for my poor English
      → Reply
    • 14 years ago, # ^ |
      ← Rev. 3   Vote: I like it +4 Vote: I do not like it

      never. and also never said that the length of the road could not be more than 1000. but if we have three cities A, B, C, and the road between AB - 1000, BC - 1000, respectively,the distance AC is greater than 1000.
      → Reply
14 years ago, # |
  Vote: I like it +1 Vote: I do not like it
Now it makes sense to me. 

Thanks everybody.
→ Reply