## 11833 - Route Change

Moderator: Board moderators

### 11833 - Route Change

Hi!
Could somebody tell to me what is wrong with my algo to this problem???

Algo:
Construct a graph,delete all edges that make a service route. Than one of the standart algo to find a shortest path form city where the vehicle was taken for repair to all others. Then find the answer! Simple test and my own it passed!

Igor9669
Learning poster

Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm

### Re: 11833 - Route Change

I got it!))
It works ok,sorry!))
Igor9669
Learning poster

Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm

### Re: 11833 - Route Change

Dude, can you explain me the problem, i am not able to understand it by reading the problem description
wazaaaap
New poster

Posts: 7
Joined: Thu Sep 23, 2010 12:55 am

### Re: 11833 - Route Change

You need to find the shortest path from one city to another with a certain condition!
Igor9669
Learning poster

Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm

### Re: 11833 - Route Change

Yes, i understood that but can you explain me the condition ?
wazaaaap
New poster

Posts: 7
Joined: Thu Sep 23, 2010 12:55 am

### Re: 11833 - Route Change

There is a service route which start at 0 and ends in (C-1) and the path is 0->1 then 1->2 .......x->(c-1)
So if you reach some city in this path you should follow only this path to reach (c-1)!
Igor9669
Learning poster

Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm

### Re: 11833 - Route Change

can someone help me please? getting WA

Code: Select all
`AC`

the problem doesn't provide sufficient I/O. so what should be the output for

Code: Select all
`7 8 6 60 1 21 2 32 3 43 4 54 5 60 6 51 6 62 6 710 12 6 60 1 21 2 32 3 43 4 54 5 60 6 51 6 62 6 76 7 07 8 08 9 89 4 70 0 0 0`

please someone help me find the case where the code fails
Last edited by Scarecrow on Tue Jul 24, 2012 2:55 am, edited 1 time in total.
Do or do not. There is no try.
Scarecrow
Learning poster

Posts: 69
Joined: Wed Oct 19, 2011 9:06 pm

### Re: 11833 - Route Change

Your code doesn't match the sample I/O.

Code: Select all
`2221`
brianfry713
Guru

Posts: 1755
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11833 - Route Change

Thnx Brianfry Such a stupid mistake i kept in my code before
Do or do not. There is no try.
Scarecrow
Learning poster

Posts: 69
Joined: Wed Oct 19, 2011 9:06 pm

### Re: 11833 - Route Change

What would be the output for this case:

Code: Select all
`7 10 4 10 1 20 6 10 5 76 5 36 1 95 4 24 3 44 6 103 2 86 2 30 0 0 0`

In my algo I remove all the edges that could form a service route, i.e. (4-0, 4-1, 4-2) and then run Dijkstra on that graph. Does that work?
afruizc
New poster

Posts: 14
Joined: Sat Oct 13, 2012 2:04 am

### Re: 11833 - Route Change

Your input is invalid, there should be roads along the service route, it is missing 1-2.

You should run Dijkstra on the graph that has roads leaving the service route removed.
brianfry713
Guru

Posts: 1755
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11833 - Route Change

Thanks for your answer. I understand why that works, but what criteria do I use to know that a path leads out of a service route. For example at node 0 there are three edges, and one of them is 0-1, and the other two are edges to "random" nodes. How do I decide which of those two nodes is the incoming edge and the outgoing one? The same case can apply for any node in the service route when there are two edges on them.

afruizc
New poster

Posts: 14
Joined: Sat Oct 13, 2012 2:04 am

### Re: 11833 - Route Change

Each road in the input is bi-directional.

The service route goes from 0 to C-1 in order. So if C is 4, there must be a road from 0 to 1, 1 to 2, and 2 to 3.

So set up the graph such that the only outgoing edge from 0 is to 1. Remove one direction of all the roads connected to the service route.
brianfry713
Guru

Posts: 1755
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11833 - Route Change

I am so dumb.

After several WA, I finally get AC. Thanks for your help Brianfry, as always you and your kindness !
afruizc
New poster

Posts: 14
Joined: Sat Oct 13, 2012 2:04 am