11377 - Airport Setup

All about problems in Volume 113. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

rifayat samee_du
New poster
Posts: 9
Joined: Tue Jul 11, 2006 8:44 am
Location: Beside you........

Re: 11377 - Airport Setup

Post by rifayat samee_du » Fri Apr 03, 2009 8:47 pm

Please give some input output
:-?
I cannot find my bug !! :( :( :( :( :(
Name : Sanzee
Location: In front of a x86 machine So...you never know may be beside you!!

rifayat samee_du
New poster
Posts: 9
Joined: Tue Jul 11, 2006 8:44 am
Location: Beside you........

Re: 11377 - Airport Setup

Post by rifayat samee_du » Sat Apr 04, 2009 8:02 am

Please any one tell me that what will be the output when x==y
if x is a city and there is no willing route then d[x] should be -1 right??
and let ,
a b c thee cities and the willing routes are a->b and a->c
and only a has airport then
if the king wants setup a route from b to b then what will be the output??
0 or 1??
Name : Sanzee
Location: In front of a x86 machine So...you never know may be beside you!!

shiplu_1320
New poster
Posts: 32
Joined: Sat Dec 29, 2007 9:08 pm
Location: CSEDU , Dhaka
Contact:

Re: 11377 - Airport Setup

Post by shiplu_1320 » Fri Apr 10, 2009 1:23 pm

when x==y output will always be 0.
A learner......

FilipeNevola
New poster
Posts: 1
Joined: Thu Sep 17, 2009 11:38 pm

Re: 11377 - Airport Setup

Post by FilipeNevola » Thu Sep 17, 2009 11:50 pm

I receive WA, I'm using Dijkstra and after I verify who was visited and no have airport.

The code is here:

Code: Select all

#include <stdio.h>
#include <string.h>
#define MAXV 2020
const int INF = 0x3F3F3F3F;

int g[MAXV][MAXV];//mat
char air[MAXV];
int pred[MAXV];
int passou[MAXV];
int custo[MAXV];
int n;

int dijkstra(int ori, int destino){
    int i, min, at;
    for(i=0;i<n;++i){pred[i]=-1;passou[i]=0;custo[i]=INF;}

    custo[ori] = 0;
    pred[ori] = ori;
    at = ori;
    while(at != destino){
        for(i=0;i<n;++i){
            if(g[at][i] != -1){
                if(custo[at] + g[at][i] < custo[i]){
                    custo[i] = custo[at] + g[at][i];
                    pred[i] = at;
                }
            }
        }
        min = INF + 1;
        passou[at] = 1;
        for(i=0;i<n;++i){
            if((custo[i] < min) && (!passou[i])){
                min = custo[i];
                at = i;
            }
        }
        if(min >= INF) return INF;
    }
    return custo[destino];
}
int main(){
    int casos,cont=0;
    int m,airs,i;
    int cons;
    scanf("%d",&casos);
    while(casos--){
        memset(g,-1,sizeof(g));
        memset(air,0,sizeof(air));
        printf("Case %d:\n",++cont);
        scanf("%d %d %d",&n,&m,&airs);

        while(airs--){
            int port;
            scanf("%d",&port);
            port--;
            air[port] = 1;
        }

        while(m--){
            int x,y;
            scanf("%d %d",&x,&y);
            x--; y--;
            g[x][y] = g[y][x] = 1;
        }

        scanf("%d",&cons);
        int res;
        while(cons--){
            int x,y;
            scanf("%d %d",&x,&y);
            x--; y--;
            int c = dijkstra(x,y);
            passou[y] = 1;
            int res = 0 ;
            if(c == INF){
                res = -1;
            }
            else{
                for(i=y;pred[i]!=i;i = pred[i]){
                    if (passou[i] && air[i] == 0){
                        res++;
                    }
                }

            }
            printf("%d\n",res);
        }
        printf("\n");
    }
}
=D

User avatar
vahid sanei
Learning poster
Posts: 84
Joined: Fri Jan 09, 2009 4:37 pm
Location: IRAN

Re: 11377 - Airport Setup

Post by vahid sanei » Tue Dec 22, 2009 6:52 pm

why when x == y answer is 0 ??? :-?
when we want to flight on same city ( you assume a journey on sky of a city with 4-example a helicopter (i didn't find Airplane word in problem statement ) )
and answer is not always 0 , it has ambiguity !
Impossible says I`m possible

nayimsust
New poster
Posts: 9
Joined: Wed Aug 27, 2008 6:50 pm

Re: 11377 - Airport Setup

Post by nayimsust » Sun Mar 21, 2010 8:47 am

is it possible to solve this problem using bfs.
if not possible then pls give me some critical input :(

yan yan
New poster
Posts: 13
Joined: Thu May 13, 2010 4:16 pm
Location: Viet Nam
Contact:

Re: 11377 - Airport Setup

Post by yan yan » Sat Jul 17, 2010 5:51 am

please give me some test case!!! :( i don't understand why i get WA!!
here is my code, is it wrong? :( :( :(

Code: Select all

#include <iostream>
#include <vector>
#include <queue>
#define lim 2010
#define maxL 999999
using namespace std;
int N , M , K , sum[lim] , x , y;
vector <int> abj[lim];
queue <int> trait;
bool air[lim] , visit[lim];

void read() //function read data
{
  int i;   
  cin >> N >> M >> K ;
  for ( i = 1 ; i <= N ; ++i)
       {
        air[i] = false;
        abj[i].clear();
       }
  for ( i = 1 ; i <= K ; ++i)     
      {
        cin >> x ;
        air[x] = true;
      }
  for ( i = 1 ; i <= M ; ++i)
      {
        cin >> x >> y;
        abj[x].push_back(y);
        abj[y].push_back(x); 
      }   
}

int solvebyBFS(int x , int y) //function caculate result
{
    if ( x == y ) return 0;
    int i , u, v;
    
    for ( i = 1 ; i <= N ; ++i)
      {
      visit[i] = false;
      sum[i] = maxL;
      }    
    if ( air[x] ) sum[x] = 0;
    else sum[x] = 1;
    
    trait.push(x);
    do {
        u = trait.front() ; trait.pop();
        visit[u] = true;      
        for ( i = 0 ; i < abj[u].size() ; ++i)
             { 
             v = abj[u][i];
             if ( !visit[v] ) 
                {
                 if ( air[v] ) {
                                   trait.push(v);
                                   sum[v] = sum[u];
                                   }
                 else if ( sum[u] + 1 < sum[v] )
                                   {
                                   sum[v] = sum[u] + 1;
                                   trait.push(v);
                                   } 
                }
             }
       }
    while ( !trait.empty() );
    
    if ( sum[y] == maxL ) return -1;
    else return sum[y];
}
int main()
{
    int tim , Query , k;
    cin >> tim;
    for ( k = 1 ; k <= tim ; ++k)
         {
         read();
         cin >> Query;
         cout << "Case " << k <<":"<<endl;
         while ( Query ) 
               {
               cin >> x >> y;
               cout << solvebyBFS(x , y) << endl;
               --Query;
               }
         if ( k != tim ) cout<< endl;
         }
    return 0;  
}
thanks avande!!! :oops: :oops:

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Location: University Of Dhaka,Bangladesh
Contact:

Re: 11377 - Airport Setup

Post by Shafaet_du » Fri Nov 05, 2010 12:40 pm

I used dijkstra to solve this problem. add a little bit dp to make the process faster. here is a tricky case:

Code: Select all

1
5 5 3
2 3 4
1 2
2 3
3 4
1 5
5 4
5
1 4
5 4
1 5
2 5
5 5
output:

Code: Select all

Case 1:
1
1
2
1
0

happy programming :wink:

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

Re: 11377 - Airport Setup

Post by raj » Sun Feb 09, 2014 12:05 am

//Accepted
Last edited by raj on Wed Feb 12, 2014 6:21 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11377 - Airport Setup

Post by brianfry713 » Wed Feb 12, 2014 1:15 am

There is a blank line between every consecutive test case.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 113 (11300-11399)”