10740 - Not the Best
Posted: Tue Oct 19, 2004 8:41 am
WA ing
Thanks !
Thanks !
My solution is BFS with Priority Queue. Is Right?
Page 1 of 2
^^
Posted: Tue Oct 19, 2004 10:23 am
I got WA, too.
My solution is BFS with Priority Queue. Is Right?
My solution is BFS with Priority Queue. Is Right?
Posted: Tue Oct 19, 2004 1:11 pm
My input:
My output:
PLZ point out my errors,
Thanks !
Code: Select all
5 6
1 5 2
1 2 1
2 5 10
1 3 1
3 5 10
1 4 1
4 5 10
5 6
1 5 3
1 2 1
2 5 10
1 3 1
3 5 10
1 4 1
4 5 10
5 6
1 5 4
1 2 1
2 5 10
1 3 1
3 5 10
1 4 1
4 5 10
5 6
1 5 5
1 2 1
2 5 10
1 3 1
3 5 10
1 4 1
4 5 10
3 3
1 3 4
1 3 3
1 2 4
2 3 5
5 6
5 2 5
1 2 2
2 5 4
3 2 3
4 3 1
5 1 3
5 4 2
2 2
1 2 3
1 2 5
2 2 2
5 6
5 2 2
1 2 2
2 5 4
3 2 3
4 3 1
5 1 3
5 4 2
5 6
5 2 3
1 2 2
2 5 4
3 2 3
4 3 1
5 1 3
5 4 2
5 6
5 2 4
1 2 2
2 5 4
3 2 3
4 3 1
5 1 3
5 4 2
5 6
5 2 5
1 2 2
2 5 4
3 2 3
4 3 1
5 1 3
5 4 2
5 6
5 2 6
1 2 2
2 5 4
3 2 3
4 3 1
5 1 3
5 4 2
5 6
5 2 7
1 2 2
2 5 4
3 2 3
4 3 1
5 1 3
5 4 2
5 6
5 2 8
1 2 2
2 5 4
3 2 3
4 3 1
5 1 3
5 4 2
5 6
5 2 9
1 2 2
2 5 4
3 2 3
4 3 1
5 1 3
5 4 2
5 6
5 2 10
1 2 2
2 5 4
3 2 3
4 3 1
5 1 3
5 4 2
0 0
Code: Select all
11
11
-1
-1
-1
15
9
6
14
15
15
16
23
24
24
24Thanks !
Posted: Tue Oct 19, 2004 3:05 pm
My AC program gives same output.
Have you considered more than one edge from between 2 vertices?
I am not sure if the judge input has such case, but the problem statment doesn't avoid that.
Have you considered more than one edge from between 2 vertices?
I am not sure if the judge input has such case, but the problem statment doesn't avoid that.
Posted: Tue Oct 19, 2004 3:32 pm
how about the case when the weight of the edge is 0. the problem says the weights are >=0;
Posted: Tue Oct 19, 2004 3:41 pm
The judge input hasn't such case , becase I had checked it.. wrote:My AC program gives same output.
Have you considered more than one edge from between 2 vertices?
I am not sure if the judge input has such case, but the problem statment doesn't avoid that.
Posted: Tue Oct 19, 2004 3:53 pm
what's the speciality of this case?abishek wrote:how about the case when the weight of the edge is 0. the problem says the weights are >=0;
Posted: Tue Oct 19, 2004 8:27 pm
there is nothing special about that case. I was just wondering if you had made that assumption some where else in the code.
Posted: Wed Oct 20, 2004 7:31 am
I changed my algorithm to BFS and got AC now
Thanks !
Thanks !
Help me!
Posted: Wed Oct 20, 2004 10:04 pm
I'm using a very naive algorithm: a simple BFS + priority queue (without checking if a node has been visited, always inserting in the queue). However, my algorithm doesn't seem to work. I was getting TLE, but now I'm getting WA. I realized that there can be zero-weighted cycles, which can cause my algo to infinite loop.
I could use some tips, inputs, or some reference to a classic kth shortest path algorithm.
I could use some tips, inputs, or some reference to a classic kth shortest path algorithm.
^^
Posted: Thu Oct 21, 2004 5:03 am
TLE...Test Case
BFS with Priority Queue can fall in local loop.4 4
1 4 10
1 2 1
2 3 1
3 1 1
1 4 10000
Some ideas
Posted: Thu Oct 21, 2004 12:20 pm
Hello sozu,
Thank you for the test case. As I said in my previous post, a zero-sized loop could be even worse
)
Thank you for the test case. As I said in my previous post, a zero-sized loop could be even worse
I tried some ideas like only inserting a node K times in the queue, but that didn't work. Could someone give some references to Kth shortest paths algorithms? I couldn't find anything really useful on the web. I would also appreciate some ideas on how to solve this problem (it's not like I want someones code, but just some ideas that could lead me to the right direction4 4
1 4 10
1 2 0
2 3 0
3 1 0
1 4 10000
)Posted: Thu Oct 21, 2004 12:45 pm
I did a simple and not too fast exhaustive search (dfs) keeping a top-k of distances from the source per node. The break-off condition for the search is when a distance outside the top-k is reached. At the end of the search the answer is in k-th place in the top-k of the target node.
A resonable speed-up (but not spectacular) was made by searching the nodes closest to the current node first (sorting the adjacency list). You can, off course, visit a node more than once during dfs.
A resonable speed-up (but not spectacular) was made by searching the nodes closest to the current node first (sorting the adjacency list). You can, off course, visit a node more than once during dfs.
Posted: Sat Oct 23, 2004 3:20 pm
Isn't there a reference for the kth shortest path after all?
Posted: Sat Oct 23, 2004 10:34 pm
What reference do you need? Isn't slightly modified Dijkstra (with counting the k-th shortest path to all the verticles) good enough?