10525 - New to Bangladesh

[anupam]

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.

[Faizur]

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.
I think your one gives-
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.

[BiK]

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?

[longer]

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]

[zsepi]

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

1

2 3
1 2 4 4
1 2 4 3
1 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?

None of the roads of Bangladesh are one ways

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?

Thanks in advance for replies.

[Per]

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.

[zsepi]

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

[little joey]

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!

[zsepi]

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.

[miras]

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>

[Guest]

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.

[helloneo]

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


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

Code: Select all

CUT AFTER AC


[helloneo]

Code: Select all

rejudged..


[Observer]

-- CUT. This task has been rejudged. --

[FAQ]

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

Code: Select all

ACed