10246 - Asterix and Obelix

[LittleJohn]

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.

[Subeen]

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

code removed

[ftomi]

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]

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]

[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]

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

[sobral]

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]

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]

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]

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]

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]

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

[Riyad]

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

[nymo]

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]

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???