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
Code: Select all
Map 1: -1
Moderator: Board moderators
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
Code: Select all
Map 1: -1
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;
}
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
Code: Select all
Map 1: 0
Map 2: -1
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;
}
This is invalid input because no. of location, L should be greater than 5.Re: 10793 - The Orc Attack
Postby spewer » Fri Dec 30, 2011 9:47 pm
Hey try this input i think is the critical one
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;
}