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!
So any advice,please!
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!
Re: 11833  Route Change
I got it!))
It works ok,sorry!))
It works ok,sorry!))
Re: 11833  Route Change
Dude, can you explain me the problem, i am not able to understand it by reading the problem description
Re: 11833  Route Change
You need to find the shortest path from one city to another with a certain condition!
Re: 11833  Route Change
Yes, i understood that but can you explain me the condition ?
Re: 11833  Route Change
There is a service route which start at 0 and ends in (C1) and the path is 0>1 then 1>2 .......x>(c1)
So if you reach some city in this path you should follow only this path to reach (c1)!
So if you reach some city in this path you should follow only this path to reach (c1)!
Re: 11833  Route Change
can someone help me please? getting WA
the problem doesn't provide sufficient I/O. so what should be the output for
please someone help me find the case where the code fails
Code: Select all
AC
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
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.

 Guru
 Posts: 5947
 Joined: Thu Sep 01, 2011 9:09 am
 Location: San Jose, CA, USA
Re: 11833  Route Change
Check input and AC output for thousands of problems on uDebug!
Re: 11833  Route Change
Thnx Brianfry Such a stupid mistake i kept in my code before
Do or do not. There is no try.
Re: 11833  Route Change
What would be the output for this case:
In my algo I remove all the edges that could form a service route, i.e. (40, 41, 42) and then run Dijkstra on that graph. Does that work?
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

 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 12.
You should run Dijkstra on the graph that has roads leaving the service route removed.
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!
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 01, 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
Thanks for your reply

 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 bidirectional.
The service route goes from 0 to C1 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.
The service route goes from 0 to C1 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!
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 !
After several WA, I finally get AC. Thanks for your help Brianfry, as always you and your kindness !