10793 - The Orc Attack

[Shafaet_du]

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]

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]

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

[mahade hasan]

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]

[raj]

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]

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