11833 - Route Change

All about problems in Volume 118. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

11833 - Route Change

Post by Igor9669 » Fri Oct 01, 2010 9:12 am

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!

So any advice,please!

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

Re: 11833 - Route Change

Post by Igor9669 » Fri Oct 01, 2010 10:46 am

I got it!))
It works ok,sorry!))

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

Re: 11833 - Route Change

Post by wazaaaap » Sat Oct 02, 2010 5:57 pm

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

Post by Igor9669 » Mon Oct 04, 2010 12:43 pm

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

Post by wazaaaap » Mon Oct 04, 2010 1:48 pm

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

Post by Igor9669 » Mon Oct 04, 2010 2:51 pm

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

Post by Scarecrow » Mon Jul 23, 2012 2:09 am

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

Post by brianfry713 » Tue Jul 24, 2012 1:59 am

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

AC output for your input:

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

Post by Scarecrow » Tue Jul 24, 2012 2:57 am

Thnx Brianfry :D Such a stupid mistake i kept in my code before :evil:
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

Post by afruizc » Sun Jan 06, 2013 7:38 pm

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

Post by brianfry713 » Mon Jan 07, 2013 4:01 am

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

Post by afruizc » Mon Jan 07, 2013 3:16 pm

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.

Thanks for your reply

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

Re: 11833 - Route Change

Post by brianfry713 » Mon Jan 07, 2013 9:51 pm

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

Post by afruizc » Tue Jan 08, 2013 2:29 am

I am so dumb. :oops:

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

Post Reply

Return to “Volume 118 (11800-11899)”