Page 2 of 4
Posted: Sun Aug 17, 2003 9:21 am
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.

Posted: Sat Oct 25, 2003 6:16 am
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.

Posted: Mon Nov 03, 2003 2:43 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?

What's wrong with the code?

Posted: Thu Nov 06, 2003 9:47 am
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[j]=r1[j]=-1;
for(i=0;i<n+1;i++)
r=r1=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[j]>=0 && r[j][k]>=0)
{
q=r[j]+r[j][k];
q1=r1[j]+r1[j][k];
if(r[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]

what hs changed since last post, 'coz WA

Posted: Sat Feb 28, 2004 8:07 pm
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?
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?

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

Posted: Sat Feb 28, 2004 10:41 pm
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.

thanks per!

Posted: Sun Feb 29, 2004 12:20 am
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

Posted: Sun Feb 29, 2004 11:13 am
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!

Posted: Sun Feb 29, 2004 7:40 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.

Posted: Thu Oct 14, 2004 4:08 pm
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>

Posted: Tue Oct 19, 2004 10:25 am
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.

Posted: Thu Dec 22, 2005 8:19 pm
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
``````

Posted: Thu Dec 22, 2005 8:43 pm

Code: Select all

``````rejudged..
``````

Posted: Fri Dec 23, 2005 6:17 am
-- CUT. This task has been rejudged. --

which prolem has been rejudged recently..?

Posted: Thu Mar 23, 2006 4:35 am
i saw many people got -1 solved problems..
anybody know which problem it is..?