10793 - The Orc Attack

[Eduard]

Unknown-error
I don't understand.

if there are any isolated node then output is -1

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

[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

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

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

[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

Output

Code: Select all

Map 1: 40

[boshkash1986]

Please can anyone help me please

[Krzysztof Duleba]

Your output for this case is ok.

[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

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

[serur]

This is misleading:

You should remember that a unit does not need to cover any distance if it remains static.

[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

[Jan]

Your cases are correct.

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

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