10246 - Asterix and Obelix
Moderator: Board moderators
-
- 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?)
Thanks in advance.
LittleJohn.
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?)
Thanks in advance.
LittleJohn.
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;
}
/* @judge_id: XXXXXX 10246 C++ "
![:(](./images/smilies/icon_frown.gif)
#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;
}
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).
Thanks in advance
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).
Thanks in advance
Last edited by broderic on Thu Sep 05, 2002 8:12 pm, edited 1 time in total.
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...
![:cry:](./images/smilies/icon_cry.gif)
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...
-
- 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
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
-
- 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
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
-
- Guru
- Posts: 1080
- Joined: Thu Dec 19, 2002 7:37 pm
-
- 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."
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
thanx in advance
Riyad
i have also checked for overflow
thanx in advance
Riyad
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN
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.
![:)](./images/smilies/icon_smile.gif)
Is this algorithm correct?
It produces WA..... Am I missing something??? Can anybody post some IO???
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();
}
}
}
}
Last edited by nymo on Thu Apr 27, 2006 10:27 pm, edited 1 time in total.