423 - MPI Maelstrom

[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

[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

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

[Ivan Golubev]

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?

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]

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]

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.

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

[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. , AC now

[chunyi81]

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]

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

[JetBrain]

What do u think will be the output to the case where i = 1 ???
(as the problem statment mentioned 1<=i<=N )

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

[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;
}

[mahade hasan]

Just change ur Line 14 as
while(scanf("%d", &n)==1)
{
your code
}
chears!

[melkiy]

Oh, boys, it requires '\n' at the end to get AC!!!

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