Page 1 of 2

423 - MPI Maelstrom

Posted: Tue Aug 13, 2002 8:23 am
by Dominik Michniewski
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:

read_data();
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

Posted: Sat Aug 17, 2002 5:05 pm
by T.T.
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[2][1]
arr[3][1] arr[3][2]
arr[4][1] arr[4][2] arr[4][3]
arr[5][1] arr[5][2] arr[5][3] arr[5][4]
then I use the Floyd's algorithm too
but I do't know why you get WA, you can check it again :)

Posted: Wed Aug 21, 2002 10:47 am
by Dominik Michniewski
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 ?

Posted: Wed Aug 21, 2002 11:17 am
by Ivan Golubev
Dominik Michniewski wrote:read_data();
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).

Posted: Thu Aug 22, 2002 8:31 am
by Dominik Michniewski
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 .... :-))

horrible runtime error!!!!!!

Posted: Thu Sep 26, 2002 2:25 pm
by Shahid
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 adj[200][200];

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

struct table
{
int known;
int dist;
int path;
} t[200];


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



while(scanf("%d\n", &n) == 1)
{
memset(adj, 0, sizeof(adj));

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);



adj[i+1][j] = k;
adj[j][i+1] = k;


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

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

else
break;
j++;
adj[i+1][j] = k;
adj[j][i+1] = k;
}
}

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(adj[v][j])
if(!t[j].known)
if((t[v].dist + adj[v][j]) < t[j].dist)
{
t[j].dist = t[v].dist + adj[v][j];
t[j].path = v+1;
}
}

// qsort(t, n, sizeof(t[0]), 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[0].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]


thanx in advance.

Posted: Fri Feb 11, 2005 8:31 am
by abhijit
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.

I need some IO :)

Posted: Sun Apr 23, 2006 6:02 pm
by nymo
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. :oops: , AC now :D

Re: I need some IO :)

Posted: Sun Jul 30, 2006 8:26 am
by chunyi81
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. :oops: , AC now :D
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.

help

Posted: Thu Oct 26, 2006 3:25 pm
by JetBrain
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];
				}
if anyone has any idea about this, let me know please..
Thanks..

Posted: Thu Oct 26, 2006 3:33 pm
by JetBrain
What do u think will be the output to the case where i = 1 ???
(as the problem statment mentioned 1<=i<=N )

423 WA :(

Posted: Thu Oct 26, 2006 4:23 pm
by JetBrain
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...

Re: 423 - MPI .... please help

Posted: Tue Feb 22, 2011 4:22 pm
by vfa88
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[110][110];

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[0][i] != INF && mini < arr[0][i])
			mini = arr[0][i];

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

	return 0;
}

Re: 423 - MPI .... please help

Posted: Sun Oct 14, 2012 8:59 pm
by mahade hasan
Just change ur Line 14 as
while(scanf("%d", &n)==1)
{
your code
}
chears!

Re: 423 - MPI .... please help

Posted: Thu Nov 07, 2013 1:10 am
by melkiy
Oh, boys, it requires '\n' at the end to get AC!!!

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