Page 2 of 3
Posted: Thu Dec 16, 2004 8:56 pm
by Eduard
Unknown-error
I don't understand.
if there are any isolated node then output is -1
Posted: Thu Dec 16, 2004 10:11 pm
by Larry
I believe they mean the same thing, since if there's an isolated node, then the rally point isn't connected to every point..
It simply means that the graph is not connected, thus, there's no rally point.
Posted: Thu Dec 16, 2004 10:40 pm
by technobug
Got it.... thanks boys
The problem was while initializing the matrix, it affected the output when I put that dist = 0 con = true..... Why?
There is no way one of the first five points is a rally point, right?
Guilherme
Posted: Fri Dec 17, 2004 6:25 am
by alu_mathics
consider the fact that the farthest point from the desired point can be the shortest distance from the first 5 five points.
example.
1 6 10
2 6 10
3 6 10
4 6 10
5 6 10
since the distance from the fr five(1,2,3,4,5) points to 6 are same that is 10, so 6 is a candidate.Again the farthest point(among the shortest) from 6 is 10.
so output 10;
finally you need to consider whether the graph matrix G[6][1...node] contains any infinity or not where 6 stands for the desired point.if yes print -1 else print the output.
Posted: Sun Mar 20, 2005 8:26 am
by windows2k
Sorry, I have a silly problem. I got confused @@
How could check the rally point equidistant from point 1 to point 5?
Any good method?
10793 The Orc Attack WA
Posted: Thu Jan 26, 2006 8:13 pm
by boshkash1986
Please can anyone send me some input and output samples
I tried everyting i could know can anyone help ?
i tried the case which was given in problem statment and here is the input and output
Input:
Code: Select all
1
10 34
1 7 12
1 9 20
2 7 12
2 3 7
2 8 10
3 2 7
3 8 10
4 8 10
4 6 4
5 9 31
5 9 20
5 7 12
6 4 4
6 10 35
6 9 16
7 1 12
7 5 20
7 9 35
7 2 12
7 8 2
8 4 10
8 2 10
8 3 10
8 7 2
8 9 10
9 8 10
9 10 40
9 6 16
9 5 20
9 5 31
9 1 20
9 7 35
10 9 40
10 6 35
Posted: Sat Jan 28, 2006 10:30 pm
by boshkash1986
Please can anyone help me please
Posted: Sat Jan 28, 2006 10:36 pm
by Krzysztof Duleba
Your output for this case is ok.
Posted: Mon Jan 30, 2006 12:04 pm
by boshkash1986
i know and that what confuses i tried alot of different cases but still i get WA
Please can you providde me with some test cases ?
Thanks
Posted: Mon Jan 30, 2006 12:15 pm
by Krzysztof Duleba
I don't have input generator for this one, but if you create some cases on your own, I can give you answers.
Posted: Fri Oct 19, 2007 9:45 pm
by serur
This is misleading:
You should remember that a unit does not need to cover any distance if it remains static.
Re: 10793 - The Orc Attack
Posted: Wed Dec 10, 2008 4:58 pm
by empo
Getting Wrong Answer
Input for the case
Code: Select all
5
7 11
1 7 2
2 7 2
3 7 2
5 7 2
6 7 1
1 6 1
2 6 1
3 6 1
4 6 1
5 6 1
7 6 1
6 1
1 2 3
7 5
1 6 1
2 6 1
3 6 1
4 6 1
5 6 1
10 17
1 9 20
1 7 12
2 3 7
2 8 10
2 7 12
3 8 10
4 8 10
4 6 4
5 7 12
5 9 20
5 9 31
6 9 16
6 10 35
7 8 2
7 9 35
8 9 10
9 10 40
6 5
1 6 10
2 6 10
3 6 10
4 6 10
5 6 10
I am getting output::
Code: Select all
Map 1: 1
Map 2: -1
Map 3: -1
Map 4: 40
Map 5: 10
Re: 10793 - The Orc Attack
Posted: Fri May 08, 2009 5:15 am
by Jan
Your cases are correct.
WA: 10793 - The Orc Attack........Plz someone help me
Posted: Mon Aug 16, 2010 4:06 pm
by ferd@u$
#include<stdio.h>
long A[1100][1100],B[1100][1100],check[1100];
long node;
void init(void)
{
long i,j;
for(i=0;i<node;i++)
{
check=0;
for(j=0;j<node;j++)
{
if(i==j)
{
A[j]=0;
B[j]=0;
}
else
{
A[j]=10000000;
B[j]=10000000;
}
}
}
return;
}
void warshall(void)
{
long k,i,j;
for (k=0 ;k<node ;k++)
{
for (i=0 ;i<node ;i++)
{
for (j=0 ;j<node ;j++)
{
if(A[j]<A[k]+A[k][j])
A[j]=A[j];
else
A[j]=A[i][k]+A[k][j];
}
}
}
/* for(i=0;i<node;i++)
{
for(j=0;j<node;j++)
printf("%ld ",A[i][j]);
printf("\n");
}*/
return;
}
int main()
{
long cost,flag,Flag,N,u,v,x,i,j,k,min,s,ii,testCase,dataSet,p,max,start,minCost,count,hand;
scanf("%ld",&testCase);
for(dataSet=1;dataSet<=testCase;dataSet++)
{
scanf("%ld %ld",&node,&N);
init();
count=0;
for(i=0;i<N;i++)
{
scanf("%ld %ld %ld",&u,&v,&cost);
u--;
v--;
if(cost<A[v])
{
A[v]=cost;
A[v]=cost;
if(u<node)
{
if(check==0)
{
check=1;
count++;
}
}
if(v<node)
{
if(check[v]==0)
{
check[v]=1;
count++;
}
}
}
}
if(count==node)
{
warshall();
Flag=start=0;
for(i=0;i<node;i++)
{
count=0;
p=-1000000;
if(A[i][0]<10000000)
{
p=A[i][0];
count++;
}
for(j=1;j<5;j++)
{
if(A[i][j]==p)
count++;
}
if(count==5)
{
if(start==0)
{
if(i!=node-1)
{
if(A[i][node-1]<10000000)
min=A[i][node-1];
else
{
if(A[i][0]<min)
min=A[i][0];
}
}
else
{
if(A[i][0]<min)
min=A[i][0];
}
start=1;
}
else
{
if(i!=node-1)
{
if(A[i][node-1]<min)
min=A[i][node-1];
else
{
if(A[i][0]<min)
min=A[i][0];
}
}
else
{
if(A[i][0]<min)
min=A[i][0];
}
}
Flag=1;
}
}
if(Flag==1)
printf("Map %ld: %ld\n",dataSet,min);
else
printf("Map %ld: -1\n",dataSet);
}
else
printf("Map %ld: -1\n",dataSet);
}
return 0;
}
WA: 10793 - The Orc Attack............Cant find the reason o
Posted: Mon Aug 16, 2010 4:17 pm
by ferd@u$
If there is only one rally point in the given map and also itself a farthest point then what will be the correct result.....
suppose for
1
6 5
6 1 1
6 2 1
6 3 1
6 4 1
6 5 1
what will be the output ???and plz give me some sample input output.........