## 10793 - The Orc Attack

Moderator: Board moderators

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Contact:

### Re: 10793 - The Orc Attack

A trivial case:

Code: Select all

``````1
5 10
1 4 6
1 5 10
2 4 12
5 6 7
1 3 8
3 9 12
2 8 12
2 6 34
3 4 54
7 9 23``````
output:

Code: Select all

``Map 1: -1``

sami001
New poster
Posts: 3
Joined: Thu Jun 17, 2010 5:19 pm

### Re: 10793 - The Orc Attack

WA...pls help me...

Code: Select all

``````#include <stdio.h>

int main(){

int loc,cost,n1,n2,c,A[105][105],CASE;
int i,j,k,n,MAX,MIN,m=1,p;
scanf("%d",&CASE);

for(p=0;p<CASE;p++){

scanf("%d%d",&loc,&cost);

for(i=1;i<=loc;i++){
for(j=1;j<=loc;j++){
A[i][j]=-1;
}
}

for(i=1;i<=loc;i++)A[i][i]=0;

for(i=0;i<cost;i++){
scanf("%d %d %d",&n1,&n2,&c);
if(A[n1][n2]==-1||A[n1][n2]>c)A[n1][n2]=A[n2][n1]=c;
}

for(k=1;k<=loc;k++){

for(i=1;i<=loc;i++){
for(j=1;j<=loc;j++){
if(A[i][k]>0 && A[k][j]>0){
if(A[i][j]>A[i][k]+A[k][j]||A[i][j]==-1){
A[i][j]=A[i][k]+A[k][j];
}
}
}
}
}

n=0;
for(i=1;i<=loc;i++){
for(j=1;j<=loc;j++){
if(A[i][j]==-1){printf("Map %d: -1\n",m);m++;n=1;break;}
}
if(n==1)break;
}
if(n==1)continue;

MIN=1000001;

for(i=6;i<=loc;i++){
n=0;
for(j=2;j<=5;j++){
if(A[i][j]!=A[i][1]){n=1;break;}
}

if(n==0){

MAX=0;
for(j=1;j<=loc;j++){
if(j==i)continue;
if(A[i][j]>MAX)MAX=A[i][j];
}

if(MAX<MIN)MIN=MAX;

}
}

printf("Map %d: ",m);

if(MIN==0||MIN>1000)printf("-1\n");
else printf("%d\n",MIN);
m++;
}
return 0;
}

``````

spewer
New poster
Posts: 4
Joined: Tue Dec 20, 2011 4:04 pm

### Re: 10793 - The Orc Attack

Hey try this input i think is the critical one

Code: Select all

``````2

5 4
1 2 0
1 3 0
1 4 0
1 5 0

5 4
1 2 1
1 3 1
1 4 1
1 5 1
``````

My Acc output this:

Code: Select all

``````Map 1: 0
Map 2: -1

``````

Learning poster
Posts: 87
Joined: Thu Dec 15, 2011 3:08 pm

### Re: 10793 - The Orc Attack

Getting Wrong Ans .....
help me!!!!

Code: Select all

``````#include<stdio.h>

int main()
{
int I,K,L,M,N,C,Tcase;
int Input[110][110];

scanf("%d",&Tcase);
for(I=1;I<=Tcase;I++)
{
scanf("%d",&N);
for(K=1;K<=N;K++)
for(L=1;L<=N;L++)
{
Input[K][L]=30000;
//Input[K][K]=0;
}
//for(K=1;K<6;K++) Input[K][K]=0;

scanf("%d",&M);
while(M--)
{
scanf("%d %d %d",&K,&L,&C);
if(Input[K][L]>C)
{
Input[K][L]=C;
Input[L][K]=C;
}
}
for(K=1; K<=N; K++)
for(L=1;L<=N;L++)
for(C=1;C<=N;C++)
if(Input[L][C]>Input[L][K]+Input[K][C])
Input[L][C]=Input[L][K]+Input[K][C];

/*for(K=1; K<=N; K++)
{printf("\n");
for(L=1;L<=N;L++)
printf("%d ",Input[K][L]);
}*/

int Flag,Ans=30000;
if(Input[1][1]+Input[1][2]+Input[1][3]+Input[1][4]+Input[1][5]==0) printf("Map %d: 0\n",I);
else
{
for(K=1;K<=N;K++)
{
Flag=0;
C=Input[1][K];
if(C<30000)
for(L=1;L<6;L++)
{
if(Input[L][K]!=C) {Flag=1;break;}
}
if(Flag==0&&Ans>Input[N][K]) Ans=Input[N][K];
}
if(Ans>=30000) printf("Map %d: -1\n",I);
else if(Ans==0) printf("Map %d: 0\n",I);
else
printf("Map %d: %d\n",I,Ans);
}

}
return 0;
}

``````
[/color]
we r surrounded by happiness
need eyes to feel it!

raj
Learning poster
Posts: 78
Joined: Fri Feb 15, 2013 5:39 pm

### Re: 10793 - The Orc Attack

Re: 10793 - The Orc Attack
Postby spewer » Fri Dec 30, 2011 9:47 pm
Hey try this input i think is the critical one
This is invalid input because no. of location, L should be greater than 5.

ssavi
New poster
Posts: 28
Joined: Thu Nov 20, 2014 9:57 pm

### Re: 10793 - The Orc Attack

What is The Problem ???? I am Getting Wrong Answer

Code: Select all

``````#include<bits/stdc++.h>
#define INF 99999999

using namespace std;

int graph[105][105];

void init()
{
for(int i=1; i<=102; i++)
{
for(int j=1; j<=102; j++)
{
if(i==j)
graph[i][j] = 0;
else
graph[i][j] = INF;
}
}
}

int main()
{
int test;
scanf("%d", &test);
for(int cs = 1; cs<=test; cs++)
{
init();
int node, edge, u, v, cost;
scanf("%d %d", &node, &edge);
for(int i=0; i<edge; i++)
{
scanf("%d %d %d", &u, &v, &cost);
graph[u][v] = graph[v][u] = min(cost, graph[u][v]);
}
for(int k=1; k<=node; k++)
{
for(int i=1; i<=node; i++)
{
for(int j=1; j<=node; j++)
{
graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);
}
}
}
/*for(int i=1; i<=node; i++)
{
for(int j=1; j<=node; j++)
{
printf("%d ", graph[i][j]);
}
printf("\n");
}*/
int cntdup = 0, mindis = INF, mini = INF;
bool in;
for(int i=6; i<=node; i++)
{
bool all = true;
in = false;
int nodecnt = 0, maxi = 0;
if( graph[i][1]<INF && graph[i][1]==graph[i][2] && graph[i][2]==graph[i][3]
&& graph[i][3]==graph[i][4] && graph[i][4]==graph[i][5])
{
nodecnt = nodecnt + 5;
mindis = min(mindis, graph[i][1]);
in = true;
}
if(in)
{
for(int j = 6; j<=node && in; j++)
{
if(graph[i][j]<INF)
{
maxi = max(maxi, graph[i][j]);
nodecnt++;
}
}
//cout<<"Node "<<i<<"= "<<maxi<<endl;
if(nodecnt==node)
{
if(in)cntdup++;
mini = min(mini, maxi);
}
}
}
if(cntdup==1) printf("Map %d: %d\n", cs, mindis);
else if(cntdup>1) printf("Map %d: %d\n", cs, mini);
else printf("Map %d: %d\n", cs, -1);

}
return 0;
}
``````
I know I am a Failure Guy .