11280 - Flying to Fredericton

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

Moderator: Board moderators

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Fri Sep 21, 2007 6:39 am

I don't get it... what did you remove?

mmonish
Experienced poster
Posts: 109
Joined: Sun Mar 11, 2007 2:55 pm
Location: SUST

Post by mmonish » Fri Sep 21, 2007 10:48 am

>>sapnil
I think this array is to small to store all the paths.

Code: Select all

S a[CSE];
change the array size.

Hope this helps.

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

Post by sapnil » Fri Sep 21, 2007 11:31 am

Again I get runtime error plz tell me why.................

//Delete

Thanks to all genious helpers

Keep posting

Sapnil

[Edited by Jan] : Use code tags.
Last edited by sapnil on Fri Sep 28, 2007 12:20 pm, edited 1 time in total.

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

Post by sapnil » Thu Sep 27, 2007 3:49 am

plz.......................................
Tell me why i ge rutime error.
plz......................

Thanks
keep posting

Sapnil

shakil
Learning poster
Posts: 74
Joined: Sat Jul 15, 2006 6:28 am
Location: CUET , bangladesh
Contact:

Post by shakil » Thu Sep 27, 2007 9:09 am

No path can be found that number of edges is geter than node.You can solve it by only find the smaller cost path then previous.
while(QuerY--)
{
scanf("%ld",&t);
if(t>Node)
t=Node;
Hope this help.
SHAKIL

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

Post by sapnil » Fri Sep 28, 2007 12:19 pm

Thank u shakil,

I think my process was not enough for pass the time limit.
Now i am thinking in dfferent process.


Thanks
Keep posting

Sapnil


http://acm.uva.es/problemset/usersnew.php?user=22910

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Sat Sep 29, 2007 3:14 am

sapnil wrote:Thank u shakil,

I think my process was not enough for pass the time limit.
Now i am thinking in dfferent process.


Thanks
Keep posting

Sapnil


http://acm.uva.es/problemset/usersnew.php?user=22910
What was your method to solve it?
The runtime should be O(nm) where n is the number of cities, and m is the number of flights.
The memory needed is only O(n+m)
Each query should take O(1) to answer

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

Post by sapnil » Sat Sep 29, 2007 6:48 pm

To sclo

I used here DFS for Genearate all paths(source to destination).
Then i search my solution,which is really time consuming.

** Now i am trying using BFS.

Thanks
keep posting
Sapnil
CSE SUST.

898989
Learning poster
Posts: 83
Joined: Wed Feb 01, 2006 12:59 pm
Location: (Fci-cu) Egypt
Contact:

Post by 898989 » Mon Jan 14, 2008 2:53 pm

Hi All, Can any one helps me in this code, I got TLE.

sp(int src, int stops) return minimum cost to reach target node(=n-1) from src.

Code: Select all

int memo[MAX][MAX], n, target;

int sp(int src, int stops) 
{
	if(src == target) 			return 0;	
	if(stops <= 0)				return OO;
	if( memo[src][stops] != -1)	return memo[src][stops];
	
	int mn = cost[src][target];
	
	for (int i = 0; i < n; ++i)
		if(i > src) 
			mn = min(mn, cost[src][i]+sp(i, stops-1) );
	
	return memo[src][stops] = mn;
}
Sleep enough after death, it is the time to work.
Mostafa Saad

mak(cse_DU)
Learning poster
Posts: 72
Joined: Tue May 30, 2006 5:57 pm
Location: bangladesh

Re: 11280 - Flying to Fredericton

Post by mak(cse_DU) » Sat Aug 30, 2008 1:03 pm

I solve it using BFS....
keeping how many node are traveled and their minimum cost.
So which algorithm you are using are not matter.
Mak
Help me PLZ!!

User avatar
tryit1
Experienced poster
Posts: 119
Joined: Sun Aug 24, 2008 9:09 pm

Re: 11280 - Flying to Fredericton

Post by tryit1 » Sat Jan 31, 2009 7:54 am

Code: Select all

2

4
Calgary
Winnipeg
Ottawa
Fredericton
6
Calgary Winnipeg 125
Calgary Ottawa 800
Winnipeg Fredericton 325
Winnipeg Ottawa 200
Calgary Fredericton 875
Ottawa Fredericton 175
4 2 1 0 10

3
Calgary
Montreal
Fredericton
2
Calgary Montreal 300
Montreal Fredericton 325
2 0 1

Code: Select all

Scenario #1
Total cost of flight(s) is $450
Total cost of flight(s) is $450
Total cost of flight(s) is $875
Total cost of flight(s) is $450

Scenario #2
No satisfactory flights
Total cost of flight(s) is $625
2 things to note.
a) there could be multiple flights between a and b.
so edge arr[a]=min(arr[a],curcost);
b) queries can be negative.
not sure about this but can have -1 stopovers.
so for each query do query=max(0,query); query=min(query,n);

SePulTribe
New poster
Posts: 28
Joined: Mon Nov 15, 2004 5:00 pm

Re: 11280 - Flying to Fredericton

Post by SePulTribe » Wed Mar 04, 2009 7:42 pm

I modified Bellman-Ford but it keeps WA-ing even though I've tried it with many different test cases, including the ones in this forum. Please help!

Code: Select all

// removed after AC
Finally got AC! I found something weird though. From all the proofs I've seen, they do not state that the order of the edges matter. They simply show that no matter what, for the ith loop of Bellman-Ford, you will have the shortest path of at most i edges in length. However, I found that (using an adjacency list) the order that the edges are relaxed matter. My implementation of the list is indexed by vertex. From there I found that you have to relax from the last vertex upwards (where node 0 is source). If you relax from vertex 0 downwards, all the changes will be propagated in just one loop or at the very least, render the result inaccurate. Hope this helps anyone in trouble. Cheers! :)

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

Re: 11280 - Flying to Fredericton

Post by Shafaet_du » Mon May 09, 2011 8:49 pm

SePulTribe is right,we need to take order into account.

queries can be negative.
not sure about this but can have -1 stopovers.
!!!!! I dont think so,my algo dont handle this.

Imran Bin Azad
New poster
Posts: 3
Joined: Thu Jun 03, 2010 8:55 pm

Re: 11280 - Flying to Fredericton

Post by Imran Bin Azad » Sat Aug 20, 2011 4:10 pm

Here, flight costs can be 0

I got this after getting no more than 7 'wa's :)

Scarecrow
Learning poster
Posts: 69
Joined: Wed Oct 19, 2011 9:06 pm

Re: 11280 - Flying to Fredericton

Post by Scarecrow » Tue Jul 24, 2012 7:42 pm

SePulTribe wrote:I modified Bellman-Ford but it keeps WA-ing even though I've tried it with many different test cases, including the ones in this forum. Please help!

Code: Select all

// removed after AC
Finally got AC! I found something weird though. From all the proofs I've seen, they do not state that the order of the edges matter. They simply show that no matter what, for the ith loop of Bellman-Ford, you will have the shortest path of at most i edges in length. However, I found that (using an adjacency list) the order that the edges are relaxed matter. My implementation of the list is indexed by vertex. From there I found that you have to relax from the last vertex upwards (where node 0 is source). If you relax from vertex 0 downwards, all the changes will be propagated in just one loop or at the very least, render the result inaccurate. Hope this helps anyone in trouble. Cheers! :)
SePulTribe, obviously in Bellman-Ford's algorithm, the order of relaxing the edges doesn't matter. But as in this problem, the algorithm have to be implemented under a constraint ( limited number of internal nodes in the shortest path), hence the order of the relaxation of the edges does matter. BTW, your observation was very helpful to me :D
Do or do not. There is no try.

Post Reply

Return to “Volume 112 (11200-11299)”