721 - Invitation Cards

[mars kaseijin]

The algo needs tweaking so that it could fit p721.
Will need some re-definition of structs to represent sample input...
otherwise, the algo takes care of the rest.

Besides this algo, i am currently implementing Dikestra's algo + weighted graph
for this problem. It will go far...

BTW, do you play free civilization for leisure?

[sds1100]

my source ->>Dikestra's algo + weighted graph ;;
why MLE and TLE . i don't know.;;
and.
up very long source
what's mean?
ac source?
that CE;;
...
T-T
help me..

[mars kaseijin]

Look, i can only show one way of doing it. (There are a few i know)
It is up to you to figure out the details.

Please make yourself useful and gimme sample inputs. Lots and lots of sample inputs!

[Vexorian]

I noticed that the reason of my TLE is that I use linked lists to represent the graph. I was unable to do otherwise because the graph can have an outstanding 1000000 of vertices, and 1000000 of edges. I can't really know if it is possible to change it to a matrix of edges per graph representation cause the problem never states the maximum degree of a bus stop.

I could just GUESS that it wouldn't have more than 5 (this way I would be very close to the memory limit) But otherwise the problem doesn't say anything about a limit so it kind of seems that even 500000 edges could be present. Then 1000000*1000000 is pretty large for the limit...

What is a good way to represent the graph for this problem?

[asif_rahman0]

use vector with pair.

[Vexorian]

Edit: My bad, I accidentally read CII as 7...


I finally got over the TLE but it is a WA now, I am unable to find a mistake, I used Dijkstra + heap.

I tested with some testcases:

Code: Select all

6
2 2
1 2 13
2 1 33
4 6
1 2 10
2 1 60
1 3 20
3 4 10
2 4 5
4 1 50
2 2
1 2 999999998
2 1 1
7 7
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
6 7 1
7 1 100
2 5
1 2 13
2 1 3
2 1 5
2 1 2
1 2 2
1 1
1 1 2

Code: Select all

46
210
999999999
636
4
0

If anyone has got more cases that could have issues please post them.

[asif_rahman0]

Just clearcut problem if you use STL.
Did you follow this:

Code: Select all

After reaching the destination stop they return empty to the originating stop

First calculate cost1, after that reverse the direction of all edges with O(p^2), then calculate the cost2.
Finally result=cost1+cost2

For case #2,(problem's)

Code: Select all

4 6
1 2 10
2 1 60
1 3 20
3 4 10
2 4 5
4 1 50

cost1=10(1-->2) + 15(1-->2-->4) + 20(1-->3) = 45
cost2=50(1-->4) + 55(1-->5-->2) + 60(1-->5-->3) =165
result=210
Btw, check the assigned value of cost(Such as cost[]=1<<30).

bye

[DD]

Just clearcut problem if you use STL.
Did you follow this:

Code: Select all

After reaching the destination stop they return empty to the originating stop

First calculate cost1, after that reverse the direction of all edges with O(p^2), then calculate the cost2.
Finally result=cost1+cost2

For case #2,(problem's)

Code: Select all

4 6
1 2 10
2 1 60
1 3 20
3 4 10
2 4 5
4 1 50

cost1=10(1-->2) + 15(1-->2-->4) + 20(1-->3) = 45
cost2=50(1-->4) + 55(1-->5-->2) + 60(1-->5-->3) =165
result=210
Btw, check the assigned value of cost(Such as cost[]=1<<30).

bye

Thanks asif_rahman0!
Your explanations are far more clear than the original problem statements. BTW, after solving this problem, I still do know the effects of time in the original problem statements, it looks like they are totally redundant.

[triplep]

well the problem seemed to be simple wen i lokked at it first...
my aprroach was this
apply dijkstra's from 1 to all other vertices
shpath(1->2)+shpath(1->3)......
then shpath from all other vertices to 1....
the answer seems to be correct...
but am getting tle...(obvoiusly cos of applying dijkstra's tat many times)
i came to know that applying dijkstra's twice is enough for the problem..
but i could not figure out why.... can some one explain me on how should i proceed... and how dijkstra's twice will do
thanks

[sady]

i used dijkstra . first handling multi edges by picking the min cost. first of all, using single source shortest path to count cost of reaching destination , secondly using single destination shortest path . Finally summing total cost
but i'm getting TLE. i used adjacency list of size vertices, 2d array for cost of each adjacent vertices .can any one help me , what thing am i missing? thanks in advance

[sady]

got accepted[img][/img]