## 10740 - Not the Best

Moderator: Board moderators

### 10740 - Not the Best

WA ing

Thanks !
liulike
Learning poster

Posts: 52
Joined: Wed Jul 30, 2003 10:56 am

### ^^

I got WA, too.

My solution is BFS with Priority Queue. Is Right?
sozu
New poster

Posts: 4
Joined: Wed Sep 29, 2004 3:22 pm
Location: Seoul

My input:
Code: Select all
`5 61 5 21 2 12 5 101 3 13 5 101 4 14 5 105 61 5 31 2 12 5 101 3 13 5 101 4 14 5 105 61 5 41 2 12 5 101 3 13 5 101 4 14 5 105 61 5 51 2 12 5 101 3 13 5 101 4 14 5 103 31 3 41 3 31 2 42 3 55 65 2 51 2 22 5 43 2 34 3 15 1 35 4 22 21 2 31 2 52 2 25 65 2 21 2 22 5 43 2 34 3 15 1 35 4 25 65 2 31 2 22 5 43 2 34 3 15 1 35 4 25 65 2 41 2 22 5 43 2 34 3 15 1 35 4 25 65 2 51 2 22 5 43 2 34 3 15 1 35 4 25 65 2 61 2 22 5 43 2 34 3 15 1 35 4 25 65 2 71 2 22 5 43 2 34 3 15 1 35 4 25 65 2 81 2 22 5 43 2 34 3 15 1 35 4 25 65 2 91 2 22 5 43 2 34 3 15 1 35 4 25 65 2 101 2 22 5 43 2 34 3 15 1 35 4 20 0`

My output:
Code: Select all
`1111-1-1-115961415151623242424`

PLZ point out my errors,

Thanks !
liulike
Learning poster

Posts: 52
Joined: Wed Jul 30, 2003 10:56 am

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.
My signature:
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.
..
A great helper

Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

how about the case when the weight of the edge is 0. the problem says the weights are >=0;

abishek
Experienced poster

Posts: 131
Joined: Mon Dec 15, 2003 5:41 am

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

The judge input hasn't such case , becase I had checked it
liulike
Learning poster

Posts: 52
Joined: Wed Jul 30, 2003 10:56 am

abishek wrote:how about the case when the weight of the edge is 0. the problem says the weights are >=0;

what's the speciality of this case?
liulike
Learning poster

Posts: 52
Joined: Wed Jul 30, 2003 10:56 am

there is nothing special about that case. I was just wondering if you had made that assumption some where else in the code.

abishek
Experienced poster

Posts: 131
Joined: Mon Dec 15, 2003 5:41 am

I changed my algorithm to BFS and got AC now

Thanks !
liulike
Learning poster

Posts: 52
Joined: Wed Jul 30, 2003 10:56 am

### Help me!

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.
Daniel
UFRN HDD-1
Brasil

danielrocha
New poster

Posts: 44
Joined: Sun Apr 27, 2003 3:17 am
Location: Rio Grande do Norte - Brazil

### ^^

TLE...Test Case

4 4
1 4 10
1 2 1
2 3 1
3 1 1
1 4 10000

BFS with Priority Queue can fall in local loop.
sozu
New poster

Posts: 4
Joined: Wed Sep 29, 2004 3:22 pm
Location: Seoul

### Some ideas

Hello sozu,

Thank you for the test case. As I said in my previous post, a zero-sized loop could be even worse

4 4
1 4 10
1 2 0
2 3 0
3 1 0
1 4 10000

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 direction )
Daniel
UFRN HDD-1
Brasil

danielrocha
New poster

Posts: 44
Joined: Sun Apr 27, 2003 3:17 am
Location: Rio Grande do Norte - Brazil

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.

little joey
Guru

Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Isn't there a reference for the kth shortest path after all?
BiK
Experienced poster

Posts: 104
Joined: Tue Sep 23, 2003 5:49 pm

What reference do you need? Isn't slightly modified Dijkstra (with counting the k-th shortest path to all the verticles) good enough?

Krzysztof Duleba
Guru

Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland

Next