Problem 3985 - Board games from the Live Archive looks like a simple application of Bellmand-Ford's algorithm.

At first I tried simply running Bellmand-Ford an if there existed a negative cycle, print "infinity." This gave me Wrong Answer. So then I noticed that there could be a negative cycle that could not lead later to the destination (I assumed the graph is directed). So I first computed the transitive-closure of the graph using Ford's algorithm and in the part of the Bellman-Ford that checks the presence of an edge (u, v) that belongs to a negative cycle, I see if edge v can take me to the destination. If this is true, then I print "infinity."

This gives me Wrong answer too! I don't know where could my program fail. Is there a very tricky case for this problem? Thank you.

## 3985 - Board games

**Moderator:** Board moderators

### 3985 - Board games

Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

http://www.dreamviews.com

**Are you dreaming right now?**http://www.dreamviews.com

### 3985 - Board games

I also did the same thing mentioned by andmej and in addition i also resubmitted the solution considering the graph to be undirected but still getting wa. Can anyone who solved this give some sample i/o (and/or tricky)?

### Re: 3985 - Board games

Apparently there are big numbers in the judge's test cases.

I finally got accepted after changing the data type used in the relaxation step in Bellman's Ford algorithm from int to long long:

Before (Gives Wrong Answer):
After (Gives Accepted):
So be careful with a possible overflow. Also, you don't need to run Transitive closure. At first this gave me time limit exceeded on the Live Archive. So I sent my code to ZJU judge which is much faster, you can practice there first and then optimize your code for the Live Archive. Good luck!

I finally got accepted after changing the data type used in the relaxation step in Bellman's Ford algorithm from int to long long:

Before (Gives Wrong Answer):

Code: Select all

```
int u = e[j].u, v = e[j].v;
int w = e[j].w;
if (d[u] + w < d[v])
d[v] = d[u] + w;
```

Code: Select all

```
int u = e[j].u, v = e[j].v;
long long w = e[j].w;
if (d[u] + w < d[v])
d[v] = d[u] + w;
```

Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

http://www.dreamviews.com

**Are you dreaming right now?**http://www.dreamviews.com

### Re: 3985 - Board games

At first I got accepted in ZJU judge but still was getting wa in uva.

After a lot of trials and errors finally i got ac with edge variable type as

I think input edge specification where

After a lot of trials and errors finally i got ac with edge variable type as

**long int**. I found that there are some inputs where*. I was relaxing edges where u and v are not equal (as i was using a adjacency matrix) and that's why was getting wa.***u = v & w != 0**I think input edge specification where

*doesn't go with the problem specification, although this is not written clearly but what does it mean by***u = v & w != 0****1 1 -100**? That means if i'm standing on square 1, my score will be -infinity? I'm requesting your attention on this issue.### Re: 3985 - Board games

I am not sure, but my program did produce "infinity" for this input:
I think the problem description has some flaws, it's very ambiguous in some parts. This holds for all problems from the problem-set that this problem belongs to (SWERC 2007).

Code: Select all

```
1
3
0 2
3
0 0 -100
0 1 1
1 2 1
```

Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

http://www.dreamviews.com

**Are you dreaming right now?**http://www.dreamviews.com