11377 - Airport Setup

[rifayat samee_du]

Please give some input output

I cannot find my bug !!

[rifayat samee_du]

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

[shiplu_1320]

when x==y output will always be 0.

[FilipeNevola]

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

[vahid sanei]

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 !

[nayimsust]

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

[yan yan]

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!!!

[Shafaet_du]

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

[raj]

//Accepted

[brianfry713]

There is a blank line between every consecutive test case.