## 10246 - Asterix and Obelix

Moderator: Board moderators

LittleJohn
Learning poster
Posts: 83
Joined: Wed Feb 27, 2002 2:00 am
Location: Taiwan
Hi,
I use Dijkstra's algorithm to implement this problem. Two arrays(one stores min cost and the other stores max food cost) are used. From the source point, update these two arrays... But it got Wrong Answer. Can somebody tell me what's wrong with this method, or what else I should pay attention to?(Or a special test case?)
LittleJohn.

Subeen
Experienced poster
Posts: 127
Joined: Tue Nov 06, 2001 2:00 am
Contact:

### 10246

this prog. got W.A. why? help!

code removed
Last edited by Subeen on Sun Oct 19, 2003 9:53 pm, edited 1 time in total.

ftomi
Learning poster
Posts: 64
Joined: Sun Jan 06, 2002 2:00 am
Location: Hungary
Contact:
Try the following:
9 9 2
1 10 5 2 3 1 1 20 1
1 2 1
2 3 1
3 6 1
1 4 2
4 5 2
5 6 2
6 7 1
7 8 1
8 9 1
1 6
1 9
0 0 0

ras46
New poster
Posts: 5
Joined: Mon Nov 05, 2001 2:00 am
Location: Taiwan
Contact:
ftomi wrote:Try the following:
9 9 2
1 10 5 2 3 1 1 20 1
1 2 1
2 3 1
3 6 1
1 4 2
4 5 2
5 6 2
6 7 1
7 8 1
8 9 1
1 6
1 9
0 0 0
My output:
9
29

Is this output correct?
If yes,why I still got a WA?

dwyak
New poster
Posts: 36
Joined: Sun Jul 28, 2002 5:16 am
Location: P.R.China
Contact:

### 10246, why i got PE

[cpp][/cpp]
/* @judge_id: XXXXXX 10246 C++ " " */
#include <fstream.h>
#include <string.h>

//ifstream fin("10246.txt");
#define fin cin
#define endl '\n'

const int MAX = 100;

int f[MAX], g[MAX][MAX], v[MAX][MAX], p[MAX];

main() {
int cases = 0, c, r, q;
for (fin >> c >> r >> q; c || r || q; fin >> c >> r >> q) {
if (cases) cout << endl;
cout << "Case #" << ++cases << endl;
int i, j, k;
for (i = 1; i <= c; i++)
fin >> f;

memset(g, 0xFF, sizeof(g));
for (i = 0; i < r; i++) {
int c1, c2, d;
fin >> c1 >> c2 >> d;
if (g[c1][c2] == -1 || d < g[c1][c2]) g[c1][c2] = g[c2][c1] = d;
}

for (i = 1; i <= c; i++) {
memset(v, 0xFF, sizeof(v)); v = 0;
memset(p, 1, sizeof(p));
for (j = 1; j < c; j++) {
int MIN = 2147383647, ID;
for (k = 1; k <= c; k++)
if (p[k] && v[k] != -1 && v[k] < MIN)
MIN = v[k], ID = k;
p[ID] = 0;
for (k = 1; k <= c; k++)
if (p[k] && f[k] <= f && g[ID][k] != -1 && (v[k] == -1 || v[i][k] > v[i][ID] + g[ID][k]))
v[i][k] = v[i][ID] + g[ID][k];
}
}

for (i = 0; i < q; i++) {
int c1, c2;
fin >> c1 >> c2;
int MIN = 2147483647;
for (j = 1; j <= c; j++)
if (v[j][c1] != -1 && v[j][c2] != -1 && v[j][c1] + v[j][c2] + f[j] < MIN)
MIN = v[j][c1] + v[j][c2] + f[j];
if (MIN > 2000000000)
cout << -1 << endl;
else
cout << MIN << endl;
}
}

return 0;
}

broderic
New poster
Posts: 34
Joined: Thu Jun 06, 2002 4:35 am
I keep getting WA on this problem...can anybody help me out?
I use floyd's (with some extra checking for the feast cost).

Here's my code (I won't leave it up too long, just for a day or two
or until somebody helps me).

Last edited by broderic on Thu Sep 05, 2002 8:12 pm, edited 1 time in total.

sobral
New poster
Posts: 2
Joined: Fri Jul 12, 2002 3:51 pm

### Hi Broderick

My first solution to this problem was very similiar to yours and I got the same problem as you: a lot of wrong answers .
One day I just thought that the floyd algorithm wasn`t doing the induction as I wanted, so I ran the floyd algorithm twice and my code got accepted.
I submitted your solution doing the same thing (calling: floyd(); floyd();) and it got accepted too. I`m not really sure why you have to run the floyd algorithm twice on this problem or if there is a solution where you can run the floyd just once.

Try it out and try to understand why it works...

broderic
New poster
Posts: 34
Joined: Thu Jun 06, 2002 4:35 am
Thanks for the idea.
Hmm, I can't think of a reason (or a test case) as to why
you need to call it twice...One more thing to think about
today.

Broderick

Amir Aavani
New poster
Posts: 30
Joined: Wed Oct 23, 2002 6:53 am
my program get WA.
i use the same method as you use.
could any one tell me what the answer of the following querry is:

3 0 1
1 2 3
1 2
3 3 0
1 2 3
1 2
1 3
2 3
9 9 2
1 10 5 2 3 1 1 20 1
1 2 1
2 3 1
3 6 1
1 4 2
4 5 2
5 6 2
6 7 1
7 8 1
8 9 1
1 6
1 9
0 0 0

my program says
Case #1
-1

Case #2

Case #3
9
29

Amir Aavani
New poster
Posts: 30
Joined: Wed Oct 23, 2002 6:53 am
at last i got AC.
my problem was due to the initialization of my array.
i use Pascal, i have an array one Mat which hold the cost of reaching from one city to the other city, at first i try to fillchar this array with 127 that means FillChar (Mat, SizeOf (Mat), 127). and get WA.

consider the following example
2 1 1
1 2
1 2 2147483645
1 2

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
You can use FillDWord(Mat, sizeof(Mat) div 4,\$7fffffff) to set an array of Integer to their maxvalue. See the Free Pascal Reference Manual for more handy functions.

I don't think the input contains these extreme cases, 'cause I use 1000000000 as the value for 'Infinity' for this problem.

koala
New poster
Posts: 7
Joined: Sun Mar 28, 2004 9:41 am
Location: Tsinghua University, Peking, P.R.China
Contact:

### something wrong with the description

It should be "Print a blank line after each case."

Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

### 10246 - Asterix and Obelix

the problem seems to be a moderated shortest path problem ..... i am getting WA frequently ......can some one give me some critical input output ...........my algorithm is dijkstra with modified relaxation function .... i have also tested for -ve weight .........but there is not any -ve weight.............can some one plizzzzzz help me with this .......
i have also checked for overflow
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

### I NEED SOME I/O'S ...

Hi, I am getting WAs with this problem. i 've tried dijkstra's shortest path algo( with some modification, off course ) and checked with some IOs. But I need more sample input and output ... please, help.

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)
Is this algorithm correct?

Code: Select all

``````while (heap is not empty)
{
Let u be the node with minimum cost
i.e. u = extractMinFromHeap();
Update data related to u(i.e. shortest path cost)

if (u == destination)
break;

for each node adjacent to u
{
Let v be a node adjacent to u

if (v is still in queue)
{
/*
RELAXATION
*/
Let cityCost be the highest cost of the feast in the path to u
and
feastCost[k] contains the cost of feast in city k

if (cityCost < feastCost[v])
{
temp = feastCost[v] - citycost;
highest cost of the feast in the path to v is feastcost[v]
}
else
{
temp = 0;
highest cost of the feast in the path to v is cityCost
}

temp = shortest[u] + temp + cost to go from u to v;

if (temp < current distance of v [in the heap])
{
HeapDecreaseKey();
}
}

}
}

``````
It produces WA..... Am I missing something??? Can anybody post some IO???
Last edited by nymo on Thu Apr 27, 2006 10:27 pm, edited 1 time in total.