## 10793 - The Orc Attack

Moderator: Board moderators

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan
Unknown-error
I don't understand.
if there are any isolated node then output is -1
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
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.

technobug
Learning poster
Posts: 88
Joined: Sat Nov 15, 2003 6:41 pm
Location: Brasilien
Contact:
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

alu_mathics
Learning poster
Posts: 55
Joined: Sat Jan 24, 2004 9:30 pm
Location: Chittagong
Contact:
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.
cuii e

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan
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?

boshkash1986
New poster
Posts: 21
Joined: Tue Jan 10, 2006 12:25 am

### 10793 The Orc Attack WA

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

Output

Code: Select all

``````Map 1: 40
``````

boshkash1986
New poster
Posts: 21
Joined: Tue Jan 10, 2006 12:25 am

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:
Your output for this case is ok.
For millions of years, mankind lived just like the animals. Then something happened which unleashed the power of our imagination. We learned to talk and we learned to listen...

boshkash1986
New poster
Posts: 21
Joined: Tue Jan 10, 2006 12:25 am
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

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:
I don't have input generator for this one, but if you create some cases on your own, I can give you answers.
For millions of years, mankind lived just like the animals. Then something happened which unleashed the power of our imagination. We learned to talk and we learned to listen...

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm
You should remember that a unit does not need to cover any distance if it remains static.
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

empo
New poster
Posts: 19
Joined: Mon Jul 28, 2008 7:00 pm
Location: India

### Re: 10793 - The Orc Attack

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
``````
"Accepted" is my passion but RTE is my weakness.....

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:

### Re: 10793 - The Orc Attack

Ami ekhono shopno dekhi...
HomePage

ferd@u\$
New poster
Posts: 4
Joined: Fri Jul 16, 2010 2:02 pm
Location: CUET
Contact:

### WA: 10793 - The Orc Attack........Plz someone help me

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

ferd@u\$
New poster
Posts: 4
Joined: Fri Jul 16, 2010 2:02 pm
Location: CUET
Contact:

### WA: 10793 - The Orc Attack............Cant find the reason o

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