### 10850 - The Gossipy Gossipers Gossip Gossips

Posted:

**Sat May 21, 2005 1:23 pm**Hi! Give me please critical input for this problem.

The Online Judge board

https://uva.onlinejudge.org/board/

Page **1** of **1**

Posted: **Sat May 21, 2005 1:23 pm**

Hi! Give me please critical input for this problem.

Posted: **Sat May 21, 2005 4:23 pm**

Make sure you've sorted the times. That was my problem during contest time.

Regards

Sanny

Regards

Sanny

Posted: **Sat May 21, 2005 6:44 pm**

Say that:

- 1 meets 4 at time 0

- 2 meets 3 at time 1

- 3 meets 4 at time 1

1 is the right answer, but some straightforward implementations might turn out to return 101.

- 1 meets 4 at time 0

- 2 meets 3 at time 1

- 3 meets 4 at time 1

1 is the right answer, but some straightforward implementations might turn out to return 101.

Posted: **Wed May 25, 2005 11:28 am**

Still WA. I receive right answer on

4 1 1

0

2 4 1

1

3 4 1

1

I use BFS search. Why here can be a problem. All the times i keep in the array c[][][], where c*[j][0]-number of times when person i meets person j.*

I post my code. Maybe someone will see some mistakes, as i'm already tired of thinking about this problem.

4 1 1

0

2 4 1

1

3 4 1

1

I use BFS search. Why here can be a problem. All the times i keep in the array c[][][], where c

I post my code. Maybe someone will see some mistakes, as i'm already tired of thinking about this problem.

Code: Select all

```
const int MAX = 21;
int c[MAX][MAX][1000];
int d[MAX];
int tmp[1000];
void main()
{
int rez,times,q,f,t,i,j,tests,people,k,NO,aa,pp,ttt;
int *z;
deque<int> Q;
scanf("%d\n", &tests);
while(tests--)
{
memset(c,0,sizeof(c));
Q.clear();
scanf("%d %d", &people, &j);
for (i=1; i<=j; i++) {
scanf("%d %d %d", &f, &t, ×);
if (f==t) { for(k=1; k<=times; k++) scanf("%d", &ttt); continue; }
for (k=1; k<=times; k++) {
scanf("%d", &aa);
c[f][t][c[f][t][0]+k] = aa;
c[t][f][c[f][t][0]+k] = aa;
}
c[f][t][0]+=times;
c[t][f][0]+=times;
}
memset(d,-1,sizeof(d));
Q.push_back(1);
d[1]=0;
while (!Q.empty()) {
q = Q[0];
Q.pop_front();
for (i=1; i<=people; i++) {
if (i==q) continue;
if (c[q][i][0]) {
for (j=1; j<=c[q][i][0]; j++) {
// fill tmp array
memset(tmp,127,sizeof(tmp));
NO = tmp[0];
if (d[q]>c[q][i][j]) tmp[j]=(d[q]/100+1)*100+c[q][i][j];
else tmp[j]=c[q][i][j];
}
z = min_element(tmp, tmp+MAX);
if (*z!=NO) {
if (d[i]==-1 || d[i]>*z) {
d[i]=*z;
Q.push_back(i);
}
}
}
}
}
rez = 0;
for(i=2; i<=people; i++) {
if (d[i]==-1) rez = -1;
else if (d[i]>rez) rez = d[i];
}
printf("%d\n", rez);
}
}
```

Posted: **Wed May 25, 2005 11:47 am**

How do you know it's still WA? I can't see that this problem has been added to volume 108 yet.oldbam wrote:Still WA.

Posted: **Wed May 25, 2005 12:56 pm**

I tested it at my home PC with the input and receive right answer

Posted: **Wed May 25, 2005 9:07 pm**

Hi! After several WAs im bagging for help

My algorithm is as follows:

I sort the times and doing simulation until there wasnt a meeting with changing news in the last 100 ticks.

I got right answers on every test case posted here and that i could think of. Maybe i missed something :/

Here comes the code:

My algorithm is as follows:

I sort the times and doing simulation until there wasnt a meeting with changing news in the last 100 ticks.

I got right answers on every test case posted here and that i could think of. Maybe i missed something :/

Here comes the code:

Code: Select all

```
```

Posted: **Wed May 25, 2005 10:57 pm**

Got the bug ...

I forgot not to start simulating when there aint no meeting ...

finally AC

thank u

I forgot not to start simulating when there aint no meeting ...

finally AC

thank u

Posted: **Thu Jun 02, 2005 3:00 am**

Hi guys,

I try to solve the 10850 and receive many WA. I think that this problem is shortest-path.

I create this output:
And my answer is

Thanks!

I try to solve the 10850 and receive many WA. I think that this problem is shortest-path.

I create this output:

Code: Select all

```
6
2 1
2 2 1
3
5 5
1 2 1
10
1 3 1
5
3 4 1
6
2 4 1
7
2 5 1
8
4 3
1 2 1
60
2 3 1
40
4 3 1
30
3 2
1 2 1
42
2 3 1
42
5 5
1 3 2
60 70
1 4 3
20 22 24
4 5 1
10
3 5 2
12 80
3 2 2
55 78
8 0
```

-1

8

230

42

80

-1

Thanks!

Posted: **Thu Jun 02, 2005 5:13 am**

Your output is correct.

Posted: **Thu Jun 02, 2005 2:12 pm**

Then what is wrong?

Do you have critical input?

Do you have critical input?

Posted: **Sun Jul 30, 2006 1:49 am**

Hi,

I don't know about shortest paths but this can be solved as a simulation problem. Just remember to increment the day only if you have visited everyone possible upto that day.

I don't know about shortest paths but this can be solved as a simulation problem. Just remember to increment the day only if you have visited everyone possible upto that day.