11280  Flying to Fredericton
Moderator: Board moderators
>>sapnil
I think this array is to small to store all the paths.
change the array size.
Hope this helps.
I think this array is to small to store all the paths.
Code: Select all
S a[CSE];
Hope this helps.
Again I get runtime error plz tell me why.................
//Delete
Thanks to all genious helpers
Keep posting
Sapnil
[Edited by Jan] : Use code tags.
//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.
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
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?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
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

 Learning poster
 Posts: 83
 Joined: Wed Feb 01, 2006 12:59 pm
 Location: (Fcicu) Egypt
 Contact:
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(=n1) from src.
sp(int src, int stops) return minimum cost to reach target node(=n1) 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, stops1) );
return memo[src][stops] = mn;
}
Sleep enough after death, it is the time to work.
Mostafa Saad
Mostafa Saad

 Learning poster
 Posts: 72
 Joined: Tue May 30, 2006 5:57 pm
 Location: bangladesh
Re: 11280  Flying to Fredericton
I solve it using BFS....
keeping how many node are traveled and their minimum cost.
So which algorithm you are using are not matter.
keeping how many node are traveled and their minimum cost.
So which algorithm you are using are not matter.
Mak
Help me PLZ!!
Help me PLZ!!
Re: 11280  Flying to Fredericton
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
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);

 New poster
 Posts: 28
 Joined: Mon Nov 15, 2004 5:00 pm
Re: 11280  Flying to Fredericton
I modified BellmanFord but it keeps WAing even though I've tried it with many different test cases, including the ones in this forum. Please help!
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 BellmanFord, 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!
Code: Select all
// removed after AC

 Experienced poster
 Posts: 147
 Joined: Mon Jun 07, 2010 11:43 am
 Location: University Of Dhaka,Bangladesh
 Contact:
Re: 11280  Flying to Fredericton
SePulTribe is right,we need to take order into account.
!!!!! I dont think so,my algo dont handle this.queries can be negative.
not sure about this but can have 1 stopovers.
UVa stats: http://felixhalim.net/uva/hunting.php?id=63448
My blog on programming: http://www.shafaetsplanet.com/planetcoding/
My blog on programming: http://www.shafaetsplanet.com/planetcoding/

 New poster
 Posts: 3
 Joined: Thu Jun 03, 2010 8:55 pm
Re: 11280  Flying to Fredericton
Here, flight costs can be 0
I got this after getting no more than 7 'wa's
I got this after getting no more than 7 'wa's
Re: 11280  Flying to Fredericton
SePulTribe, obviously in BellmanFord'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 meSePulTribe wrote:I modified BellmanFord but it keeps WAing even though I've tried it with many different test cases, including the ones in this forum. Please help!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 BellmanFord, 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!Code: Select all
// removed after AC
Do or do not. There is no try.