## 11833 - Route Change

Moderator: Board moderators

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

### 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!))

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

### Re: 11833 - Route Change

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

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

### Re: 11833 - Route Change

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

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

### Re: 11833 - Route Change

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

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

### 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)!

Scarecrow
Learning poster
Posts: 69
Joined: Wed Oct 19, 2011 9:06 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 6
0 1 2
1 2 3
2 3 4
3 4 5
4 5 6
0 6 5
1 6 6
2 6 7
10 12 6 6
0 1 2
1 2 3
2 3 4
3 4 5
4 5 6
0 6 5
1 6 6
2 6 7
6 7 0
7 8 0
8 9 8
9 4 7
0 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.

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

### Re: 11833 - Route Change

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

Code: Select all

``````22
21``````
Check input and AC output for thousands of problems on uDebug!

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

### Re: 11833 - Route Change

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

afruizc
New poster
Posts: 15
Joined: Sat Oct 13, 2012 2:04 am

### Re: 11833 - Route Change

What would be the output for this case:

Code: Select all

``````7 10 4 1
0 1 2
0 6 1
0 5 7
6 5 3
6 1 9
5 4 2
4 3 4
4 6 10
3 2 8
6 2 3
0 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?

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

### 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.
Check input and AC output for thousands of problems on uDebug!

afruizc
New poster
Posts: 15
Joined: Sat Oct 13, 2012 2:04 am

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

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

### 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.
Check input and AC output for thousands of problems on uDebug!

afruizc
New poster
Posts: 15
Joined: Sat Oct 13, 2012 2:04 am

### 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 !