## 423 - MPI Maelstrom

Moderator: Board moderators

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

### 423 - MPI Maelstrom

Could anyone say me, why Floyd is wrong in this problem ?
I try to solve it using Floyd and got WA many times My code is very simple:

Floyd();
found longest path from all paths to all other nodes in table of shortest path ....

could anyone tell me any traps in this problem ??

Best regards
Dominik

T.T.
New poster
Posts: 12
Joined: Mon Dec 31, 2001 2:00 am
Location: Taiwan
I get the input carefully, in it's input
5
50
30 5
100 20 50
10 x x 10
every number represent ( except the size 5 )
arr
arr arr
arr arr arr
arr arr arr arr
then I use the Floyd's algorithm too
but I do't know why you get WA, you can check it again Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
Only one thing, which I can imagine, is 'X' in input. I set this 'x' as MAX_INT-1 (2.000.000.000 and something ) - maybe it's wrong ?

Ivan Golubev
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia
Floyd();
found longest path from all paths to all other nodes in table of shortest path ....
Are you searching all paths or you searching all paths from first processor to all other processors as it needed by problem description?
Dominik Michniewski wrote:Only one thing, which I can imagine, is 'X' in input. I set this 'x' as MAX_INT-1 (2.000.000.000 and something ) - maybe it's wrong ?
I'm not sure that there is an input like 2^31-1 but I've used zero for value of 'x' and it was OK.
Also I've used Dijkstra not Floyd because we need not all paths only ones that goes from first processor(node).

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
Thanks all for help I got accepted yesterday But I still don't know why my previous code got WA. I change only two things: don't set way to unrecheable nodes to INT-MAX - 1 and print 0 if from node 1 I can't walk to some else node .... )

Shahid
Learning poster
Posts: 68
Joined: Fri Oct 26, 2001 2:00 am
Contact:

### horrible runtime error!!!!!!

i submitted 423 agin and agin and evrything seems ok except the judges response(offcourse i don't want to say that the judge is wrong) ...but i get all the time runtime error. can anyone help me..... at first i thought the problem may be regarding the qsort function, so i change i, but no change....bellow in the code i commented the previous qsort portion...

here is my code:
[c]

/*@BEGIN_OF_SOURCE_CODE*/

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int sort_function( const void *a, const void *b);

struct table
{
int known;
int dist;
int path;
} t;

void main()
{
int i, j, k, n, start = 1;
char str, *p;

while(scanf("%d\n", &n) == 1)
{

for(i = 0; i < n-1; i++)
{
j = 0;
strcpy(str, "");
gets(str);

p = strtok(str, " ""\t");

if(p)
if(!strcmp(p, "x"))
k = 0;
else
k = atoi(p);

for(;;)
{
p = strtok(NULL, " \t");

if(p)
{
if(!strcmp(p, "x"))
k = 0;
else
k = atoi(p);
}

else
break;
j++;
}
}

for(i = 0; i < n; i++)
{
t.known = 0;
t.dist = 9999;
t.path = 0;
}

t[start-1].dist = 0;

int min = 10000, flag = 0, v;

for(;;)
{
flag = 0;
min = 10000;
for(i = 0; i < n; i++)
if(!t.known)
{
if(t.dist < min)
{
min = t.dist;
v = i;
}
flag = 1;
}

if(!flag)
break;

t[v].known = 1;

for(j = 0; j < n; j++)
if(!t[j].known)
{
t[j].path = v+1;
}
}

// qsort(t, n, sizeof(t), sort_function);

int max = 0;
for(i = 0; i < n; i++)
if(t.dist > max)
max = t.dist;

printf("%d\n", max);

// printf("%d\n", t.dist);
}
}

int sort_function( const void *a, const void *b)
{
struct table aa, bb;

aa = *(struct table *)a;
bb = *(struct table *)b;

if(aa.dist < bb.dist)
return 1;
if(aa.dist > bb.dist)
return -1;
else
return 1;
}

/*@END_OF_SOURCE_CODE*/

[/c]

abhijit
New poster
Posts: 12
Joined: Mon May 24, 2004 2:13 pm
Yes, with floyds, one must never set no-link to INT_MAX-1 or somewhere close.
Since, the algo has a line like :
mat[k]+mat[k][j]
This will lead to an overflow in range, and will wrap to a negetive value, making your algo fail.

So make sure that 2*YOUR_MAX <= INT_MAX.

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

### I need some IO :)

Hi, I 've implemented dijkstra algo. with binary heap and want to check whether it produces correct answer... so, I try 423 and get WA I need some tricky IO on this problem... thanks.

[EDIT] My implementation of Dijkstra is okay, it was a silly mistake on the input part. , AC now chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

### Re: I need some IO :)

nymo wrote:Hi, I 've implemented dijkstra algo. with binary heap and want to check whether it produces correct answer... so, I try 423 and get WA I need some tricky IO on this problem... thanks.

[EDIT] My implementation of Dijkstra is okay, it was a silly mistake on the input part. , AC now I used Dijkstra for this problem as well, because we only need the longest transmission time from processor 1 to all other processors. Single-source is sufficient for this problem. Floyd is ok, but I think it is a bit of an overkill since Dijkstra can be used for finding all shortest paths from a single souce.

JetBrain
New poster
Posts: 15
Joined: Sun Jul 23, 2006 4:24 pm
Location: Cairo, Egypt
Contact:

### help

Dominik Michniewski wrote:Only one thing, which I can imagine, is 'X' in input. I set this 'x' as MAX_INT-1 (2.000.000.000 and something ) - maybe it's wrong ?
Hi Dominik & T.T.
I used the same method u used to solve this problem.. but I'm still getting WA.. I use -1 instead of 'x' & add a condition to neglect it while trying to solve using warshall algorithm..

Code: Select all

``````if (d[i][k] + d[k][j] < d[i][j] && d[i][k] >= 0 && d[k][j] >= 0)
{
d[i][j] = d[i][k] + d[k][j];
p[i][j] = p[k][j];
}
``````
Thanks..

JetBrain
New poster
Posts: 15
Joined: Sun Jul 23, 2006 4:24 pm
Location: Cairo, Egypt
Contact:
What do u think will be the output to the case where i = 1 ???
(as the problem statment mentioned 1<=i<=N )

JetBrain
New poster
Posts: 15
Joined: Sun Jul 23, 2006 4:24 pm
Location: Cairo, Egypt
Contact:

### 423 WA :(

I've been trying to solve this problem , but I keep getting WA Please if anyone has sample tricky inputs, I'll be really so grateful..

I'm using warshall algo..
please help me cause I really fed up Thanks...

vfa88
New poster
Posts: 1
Joined: Tue Feb 22, 2011 4:19 pm

Hi all,

I have been having some trouble with this particular problem. I kept looking through my code but I see no problems with it.

Basically, I'm using Floyd Warshall and I iterate through the first row (shortest distance from first node to all other nodes) and I find the maximum. But still WA.

Can someone help me? Thanks!

Code: Select all

``````#include <iostream>
#include <cmath>
#define INF 1000000000

using namespace std;

int arr;

int main()
{
//freopen("in.txt", "r", stdin);
int n;

scanf("%d", &n);
for(int i = 0; i < n; ++i)
for(int j = 0; j < n; ++j)
arr[i][j] = INF;

for(int i = 0; i < n; ++i)
{
arr[i][i] = 0;
for(int j = 0; j < i; ++j)
{
while(cin.peek() == ' ') cin.get();
if(cin.peek() == 'x')
{
cin.get();
continue;
}
scanf("%d", &arr[i][j]);
arr[j][i] = arr[i][j];
}
}

for(int k = 0; k < n; ++k)
for(int i = 0; i < n; ++i)
for(int j = 0; j < n; ++j)
arr[i][j] = min(arr[i][j], arr[i][k] + arr[k][j]);

int mini = 0;
for(int i = 0; i < n; ++i)
if(arr[i] != INF && mini < arr[i])
mini = arr[i];

printf("%d\n", mini);

return 0;
}``````

Learning poster
Posts: 87
Joined: Thu Dec 15, 2011 3:08 pm

Just change ur Line 14 as
while(scanf("%d", &n)==1)
{
}
chears!
we r surrounded by happiness
need eyes to feel it!

melkiy
New poster
Posts: 1
Joined: Thu Nov 07, 2013 1:04 am