423  MPI Maelstrom
Moderator: Board moderators

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

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

 Experienced poster
 Posts: 167
 Joined: Fri Oct 19, 2001 2:00 am
 Location: Saint Petersburg, Russia
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:read_data();
Floyd();
found longest path from all paths to all other nodes in table of shortest path ....
I'm not sure that there is an input like 2^311 but I've used zero for value of 'x' and it was OK.Dominik Michniewski wrote:Only one thing, which I can imagine, is 'X' in input. I set this 'x' as MAX_INT1 (2.000.000.000 and something )  maybe it's wrong ?
Also I've used Dijkstra not Floyd because we need not all paths only ones that goes from first processor(node).

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

 Learning poster
 Posts: 68
 Joined: Fri Oct 26, 2001 2:00 am
 Location: Dhaka, Bangladesh
 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 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 < n1; 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[start1].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.
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 < n1; 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[start1].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.
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
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
Re: I need some IO :)
I used Dijkstra for this problem as well, because we only need the longest transmission time from processor 1 to all other processors. Singlesource 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.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
help
Hi Dominik & T.T.Dominik Michniewski wrote:Only one thing, which I can imagine, is 'X' in input. I set this 'x' as MAX_INT1 (2.000.000.000 and something )  maybe it's wrong ?
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..
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...
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
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!
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;
}

 Learning poster
 Posts: 87
 Joined: Thu Dec 15, 2011 3:08 pm
 Location: University of Rajshahi,Bangladesh
Re: 423  MPI .... please help
Just change ur Line 14 as
while(scanf("%d", &n)==1)
{
your code
}
chears!
while(scanf("%d", &n)==1)
{
your code
}
chears!
we r surrounded by happiness
need eyes to feel it!
need eyes to feel it!
Re: 423  MPI .... please help
Oh, boys, it requires '\n' at the end to get AC!!!
printf("%d\n", answer);
printf("%d\n", answer);