11833 - Route Change

[Igor9669]

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]

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

[wazaaaap]

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

[Igor9669]

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

[wazaaaap]

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

[Igor9669]

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]

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

[brianfry713]

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

AC output for your input:

Code: Select all

22
21

[Scarecrow]

Thnx Brianfry Such a stupid mistake i kept in my code before

[afruizc]

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]

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.

[afruizc]

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]

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.

[afruizc]

I am so dumb.

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