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

Giorgi
New poster
Posts: 48
Joined: Wed Jun 07, 2006 6:26 pm
Location: Georgia Tbilisi

11377 - Airport Setup

Post by Giorgi » Sat Jan 05, 2008 7:26 pm

this problem makes me crazy...
I can't understand why simple soltion with BFS did not get AC.
is there any tricky case or I can't understand problem statement well?

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Sat Jan 05, 2008 8:21 pm

Does your code handle the case x==y ?

-----
Rio

Giorgi
New poster
Posts: 48
Joined: Wed Jun 07, 2006 6:26 pm
Location: Georgia Tbilisi

Post by Giorgi » Sat Jan 05, 2008 8:38 pm

rio wrote:Does your code handle the case x==y ?
Yes

here is my code, maybe I have very stupid mistake , but I can't find it...

Code: Select all

I was Code :)
Last edited by Giorgi on Sat Jan 05, 2008 9:43 pm, edited 1 time in total.

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Sat Jan 05, 2008 9:10 pm

Giorgi wrote:
rio wrote:Does your code handle the case x==y ?
Yes
No. Your code is not handling it correctly.

For input:

Code: Select all

1
2 1 1
1
1 2
1
2 2
You must output 0.
-----
Rio

Giorgi
New poster
Posts: 48
Joined: Wed Jun 07, 2006 6:26 pm
Location: Georgia Tbilisi

Post by Giorgi » Sat Jan 05, 2008 9:34 pm

thank you I got AC. very stupid mistake :(

joshi13
New poster
Posts: 9
Joined: Sun Jan 06, 2008 3:18 am

Graph

Post by joshi13 » Sun Jan 06, 2008 3:23 am

Hi, i'm wondering how would be the graph you're working with, how to construct it. It would be very helpful.
Also please post some I/O cases.

Thanks for replies.

srrajesh
New poster
Posts: 23
Joined: Sun Sep 30, 2007 9:02 pm

Post by srrajesh » Sun Jan 06, 2008 10:49 am

I first implemented BFS, but that gave WA, even after considering x == y case.
So I implemented Djkstra noting that if x and y don't have an airport then the cost of path between them will be more than, if any one of them have airport which in turn will be more when, both have airport in it.
Is this approach correct?
I am getting continuous WAs
This is my first implementation of Djkstra, so I think there might be some problem with the implementation.

Code: Select all

Code removed after getting AC
Thanks in advance for your help.
Last edited by srrajesh on Sun Jan 06, 2008 12:59 pm, edited 1 time in total.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Sun Jan 06, 2008 11:06 am

srrajesh wrote:So I implemented Djkstra noting that if x and y don't have an airport then the cost of path between them will be more than, if any one of them have airport which in turn will be more when, both have airport in it.
Is this approach correct?
As you implemented it, no.
At very least you should assign a cost of 0 to edges with two airports, or else your solution would always prefer shorter paths to longer ones, even if longer paths would require to build less airports.

Here's one correct approach: let cost of directed edge a->b be 1 if b doesn't have an airport, and 0 otherwise; each undirected edge (a, b) corresponds to two symmetric directed edges: a->b and b->a.
Then the answer is length of shortest path between x and y, plus 1 if x doesn't have an airport.

srrajesh
New poster
Posts: 23
Joined: Sun Sep 30, 2007 9:02 pm

Post by srrajesh » Sun Jan 06, 2008 12:05 pm

mf wrote: Here's one correct approach: let cost of directed edge a->b be 1 if b doesn't have an airport, and 0 otherwise; each undirected edge (a, b) corresponds to two symmetric directed edges: a->b and b->a.
Then the answer is length of shortest path between x and y, plus 1 if x doesn't have an airport.
I implemented as you said now, but still WA.
In my previous post, I had a very serious bug!
I had declared "arr" adjacency matrix as bool, so no effect of assigining it any non-zero value to it!
Indeed, it is a very stupid mistake.
I corrected it as char and resubmitted it with the idea you said, but still I am getting WA.
In previous posts, people say that they solved with BFS. If so can anyone give me an idea.

Code: Select all

Code removed after getting AC
Last edited by srrajesh on Sun Jan 06, 2008 12:58 pm, edited 1 time in total.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Sun Jan 06, 2008 12:25 pm

*Always* remember to test your code on sample I/O, especially before posting it here.
It prints extra newlines.
srrajesh wrote:In previous posts, people say that they solved with BFS. If so can anyone give me an idea.
You can find shortest paths in graphs with edge weights 0 and 1 with a modification of BFS: instead of a queue use deque, when you process an edge of cost 1, insert the new node at the back (as in BFS), else at the front of the deque.

srrajesh
New poster
Posts: 23
Joined: Sun Sep 30, 2007 9:02 pm

Post by srrajesh » Sun Jan 06, 2008 12:57 pm

mf wrote:*Always* remember to test your code on sample I/O, especially before posting it here.
It prints extra newlines.
I got AC now
Thanks a million!
I added some debugging statements, and then I deleted them, but I forgot to remove the newline I had given as a part of that.
I should have tested by redirecting the o/p to a file, before posting. Thanks a million for your help.
mf wrote: You can find shortest paths in graphs with edge weights 0 and 1 with a modification of BFS: instead of a queue use deque, when you process an edge of cost 1, insert the new node at the back (as in BFS), else at the front of the deque.
Thanks for the idea.
If I understand correctly, I think this concept applies when the weights are 0 and any other value >= 1.

hsn
New poster
Posts: 4
Joined: Thu Jan 24, 2008 12:56 am

Post by hsn » Tue Jan 29, 2008 11:30 am

hello everyone i really need some help here
i have done this problem by using floyd algorithm
i don't know if this is the correct approch or not.
when i give 2000 cities it take alot of time for the code to finish so it is very slow.
what is the best way to solve this question and why??????????????
plzzzzzz help me i really need to solve this question.

thank in advance

sapnil
Experienced poster
Posts: 106
Joined: Thu Apr 26, 2007 2:40 pm
Location: CSE-SUST
Contact:

Post by sapnil » Fri Feb 15, 2008 2:53 pm

I use simple dijkstra, But till WR
Here my code

Code: Select all

// Code removed

Thanks
Keep Posting
Sapnil
"Dream Is The Key To Success"

@@@ Jony @@@

User avatar
kbr_iut
Experienced poster
Posts: 103
Joined: Tue Mar 25, 2008 11:00 pm
Location: IUT-OIC, DHAKA, BANGLADESH
Contact:

Re: 11377 - Airport Setup

Post by kbr_iut » Mon Nov 24, 2008 11:17 pm

thanku mf.
I got AC using dijsktra with ur explanation.
It is tough to become a good programmer.
It is more tough to become a good person.
I am trying both...............................

tanmoy
New poster
Posts: 18
Joined: Wed Jun 25, 2008 2:25 pm

Re: 11377 - Airport Setup

Post by tanmoy » Tue Jan 06, 2009 3:09 am

can any one help me about this problem plz

Code: Select all

#include<stdio.h>
#include<memory.h>
#include<iostream>
#include<queue>
using namespace std;
#define MAX 2002
int adj[MAX][MAX];
int P[MAX+3],O[MAX];
bool T[MAX];
int n,s,d,counter,v=0;

void BFS (void){
	int x,i,c=0;
	bool flag=false;
	fill(P,P+n+2,0);
	queue<int> Q;
	Q.push(s);
	P[s]=1;
	O[s]=0;
	while(!Q.empty()&&Q.back()!=d){
		x=Q.front();
		Q.pop();
		for(i=1;i<=n;i++){
			if(adj[x][i]==1 && P[i]==0){
				P[i]=1;
				Q.push(i);
				O[i]=x;
				if(Q.back()==d){flag=true;break;}
			}
		}
	}
	v++;
	printf("Case %d:\n",v);
	if(flag==false && s!=d ){printf("-1\n");return ;}
	else if(s==d){
			printf("0\n");
			return;
	}
		counter=0,i=1;
		if(T[d]==false)counter++;
		x=d;
		while(1){
			x=O[x];
			if(T[x]==false)counter++;
			if(x==s) break;
			x=O[x];
			if(T[x]==false)counter++;
			if(x==s )break;
		}
		printf("%d\n",counter);


}






int main(){
	int X,N,M,K,i,g;
	scanf("%d",&X);
	while(X--){
		memset(T,false,sizeof(T));
		scanf("%d %d %d",&N,&M,&K);
		n=N;
		for(i=1;i<=N;i++){
			memset(adj[i],0,sizeof(int)*N);
		}
		for(i=0;i<K;i++){
			scanf("%d",&g);
			T[g]=true;
		}
		for(i=0;i<M;i++){
			scanf("%d %d",&g,&K);
			adj[g][K]=1;
			adj[K][g]=1;
		}
		scanf("%d",&K);
		while(K--){
			scanf("%d %d",&s,&d);
			BFS();
		}
	}
	return 0;
}

Post Reply

Return to “Volume 113 (11300-11399)”