## 10525 - New to Bangladesh

Moderator: Board moderators

Dear Noim,
When the contest was held, the statement was made clear by writing that
1)you should determine first sht est time.
2)if there is more than one path you should choose the shortest distance. among them.
and again, i made contact with them about the bug but they are very busy now with their new server and they give much more time in real time contest than in 24 hrs. so i posted in the board first and then after a lot of discussion till my post i think it's clear. any1 just watched once in the posts can easily find it and fix his/her bugs. and rejudgement was a hard work. that is why i have no other ways. for example, the sample out was wrong for the prob height to area. but as they are working, look at the boards please.
"Everything should be made simple, but not always simpler"
anupam
A great helper

Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm

carneiro,
I think your Program give WA for input like-
1

2 2
1 2 4 5
1 2 5 5
1
1 2
My AC code says output should be:
Distance and time to reach destination is 5 & 5.
Distance and time to reach destination is 4 & 5.
There is obviously some bugs in the problem.To get AC you have to overwrite the edges.
Faizur
New poster

Posts: 39
Joined: Fri Jun 06, 2003 3:04 pm

I am very teased with this problem. My program passes all test data I found on the forum or devised myself. What does overwriting edges mean?
BiK
Experienced poster

Posts: 104
Joined: Tue Sep 23, 2003 5:49 pm

### What's wrong with the code?

I also tried some other combinations when the edges are over written. But all got WA.

int m,n;
//vector<int> nms;
int r[100][100];
int r1[100][100];

void main()
{
int t;
int i,j,k;
int q,q1;
int nm1,nm2;
cin>>t;
while(t)
{
//nms.clear();
cin>>n>>m; if(n>=100) m=n/(i-i);
for(i=0;i<n+1;i++)
for(j=0;j<n+1;j++)
r[i][j]=r1[i][j]=-1;
for(i=0;i<n+1;i++)
r[i][i]=r1[i][i]=0;
for(i=0;i<m;i++)
{
cin>>j>>k;
if(j>n || j<=0 || k>n || k<=0) m=m/(i-i);
cin>>q>>q1;
if(r[j][k]<0 || q<r[j][k] || (q==r[j][k] && q1<r1[j][k]))
{
r[j][k]=r[k][j]=q;
r1[j][k]=r1[k][j]=q1;
}
}
//n=nms.size();
for(k=0;k<=n;k++)
for(i=0;i<=n;i++)
for(j=0;j<=n;j++)
if(r[i][j]>=0 && r[j][k]>=0)
{
q=r[i][j]+r[j][k];
q1=r1[i][j]+r1[j][k];
if(r[i][k]<0 || q<r[i][k] || (q==r[i][k] && q1<r1[i][k]))
{
r[i][k]=q;
r1[i][k]=q1;
}
}

cin>>q;
for(i=0;i<q;i++)
{
cin>>j>>k;
if(j>n || k>n ||j<=0 || k<=0) m=n/(i-i);
if(j<0 || k<0 || r[j][k]<0) cout<<"No Path."<<endl;
else cout<<"Distance and time to reach destination is "<<r1[j][k]<<" & "<<r[j][k]<<"."<<endl;
}
t--;
if(t) cout<<endl;
}
}
[cpp][/cpp][cpp][/cpp]
longer
New poster

Posts: 2
Joined: Thu Nov 06, 2003 9:44 am

### what hs changed since last post, 'coz WA

I keep getting WA and it frustrates me quite a lot (not surprising, eh?)
After reading the forum, I became even more confused (usually the opposite happens), so I would like to ask a few questions

1) edge overwriting
So, when I add an edge, I should always keep the latest one, or should I keep the edge with shortest time and if time is same with, then overwrite only if new edge has shorter distance than existent one?
ie: if input is
Code: Select all
`12 31 2 4 41 2 4 31 2 5 5`

which is the right edge to use?

2) finding shortest path
I think it's clear, but just to be safe: the program should look for the minimal time with the shortest length, right? so, is the following comparison right:
[c]if(currentTime <= bestTimeSoFar) {
if(currentTime < bestTimeSoFar || currentDistance < bestDistanceSoFar)
update shortest path
}[/c]

3) we are dealing with an undirected graph, right?

4) What is the maximum length of a shortest path?
I am using floyd-warshall to solve the problem, and i use infinity = 1 << 30 - there is no chance that a shortest path will be this long or longer, right?

Dealing with failure is easy: Work hard to improve.
Success is also easy to handle: You've solved the wrong problem. Work hard to improve.
zsepi
Learning poster

Posts: 51
Joined: Thu Sep 26, 2002 7:43 pm
Location: Easton, PA, USA

### Re: what hs changed since last post, 'coz WA

1) Always the last one, for some obscure reason. I.e. 1 2 5 5 in this case.

2) Yup, that should work.

3) Yup.

4) I actually use 2^61 as infinity. I'm not sure this is something I did out of sheer paranoia when I got WA, or if it is actually needed.
Per
A great helper

Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

### thanks per!

it's not paranoia..... 2^61 seems to be the right value for infinity. That was the only thing I changed, and got ac... stupid stupid bug
Dealing with failure is easy: Work hard to improve.
Success is also easy to handle: You've solved the wrong problem. Work hard to improve.
zsepi
Learning poster

Posts: 51
Joined: Thu Sep 26, 2002 7:43 pm
Location: Easton, PA, USA

I use a value of 1e9 for infinity and get accepted, so I don't think you need 64 bits. The thing is that during Floyd you do something like[c]newdist=dist[from][intermediate]+dist[intermediate][to];
if(newdist<dist[from][to]) dist[from][to]=newdist;[/c] so you should be able to deal with double infinity. If you use 32-bits signed integers and 2^30 as value for infinity, than newdist can become 2^30+2^30 = 2^31, which is smaller than zero!

little joey
Guru

Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

little joey wrote:If you use 32-bits signed integers and 2^30 as value for infinity, than newdist can become 2^30+2^30 = 2^31, which is smaller than zero!

joey, I'm aware of that problem, that's why I have in the comparison
Code: Select all
`if(g[from][intermed].time != INF  &&  g[intermed]toj].time != INF) {               time = g[from][intermed].time + g[intermed][to].time;               ....`

so I don't know why, but when I changed the type of time from int to long long and "increased infinity", I got AC without any other modification and that made me think that 2^30 is not big enough.
Dealing with failure is easy: Work hard to improve.
Success is also easy to handle: You've solved the wrong problem. Work hard to improve.
zsepi
Learning poster

Posts: 51
Joined: Thu Sep 26, 2002 7:43 pm
Location: Easton, PA, USA

you don't have to use 2^61 you can just use 2^31-1 as infinity....

I got WA at the contest and after one year i got AC... <yupi>
Remember Never Give Up
Miras
miras
Learning poster

Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm

Hello,
Can anyone help me by answering the following questions:

1. The problem statement says "Places are numbered starting from 1.", does this mean 1 <= place_number <= max_node? Or do I need to map the numbers?
Ans: No need to map.

2. I'm using Floyd-Warshall, what could be the limit for maxnode and INF? I'm using 300 and 1000000000, respectively.
Ans: 200 is enough.

3. Is the following code segment correct? I'm using it in my Floyd-Warshall function.

Code: Select all
` .. `

Thank you.
Guest
New poster

Posts: 39
Joined: Wed May 19, 2004 5:52 pm

### 10525 - NEW TO BANGLADESH?

i think my code is handling the duplicated roads very well.. but getting WA!!

map[][] is for time..
map2[][] is for distance..

Code: Select all
`CUT AFTER AC`
Last edited by helloneo on Fri Jun 08, 2007 6:10 am, edited 3 times in total.
helloneo
Guru

Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Code: Select all
`rejudged..`
Last edited by helloneo on Thu Mar 23, 2006 1:14 pm, edited 1 time in total.
helloneo
Guru

Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

-- CUT. This task has been rejudged. --
Last edited by Observer on Sat Mar 25, 2006 7:12 pm, edited 1 time in total.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
Observer
Guru

Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

### I still got WA :(

could anyone tell me some tricky tests please? I have just searched forum for it

Code: Select all
`ACed`
Last edited by FAQ on Thu Mar 30, 2006 1:17 pm, edited 1 time in total.
FAQ
Learning poster

Posts: 84
Joined: Wed Jan 28, 2004 6:23 pm

PreviousNext