11280 - Flying to Fredericton

[Darko]

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

[mmonish]

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

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

//Delete

Thanks to all genious helpers

Keep posting

Sapnil

[Edited by Jan] : Use code tags.

[sapnil]

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

Thanks
keep posting

Sapnil

[shakil]

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.

[sapnil]

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]

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]

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]

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;
}

[mak(cse_DU)]

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

[tryit1]

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]

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]

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]

Here, flight costs can be 0

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

[Scarecrow]

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