11374 - Airport Express

[jurajz]

In contest, I tried Floyd-Warshall, but TLE. Then I had idea in O(n^2) but it seems wrong.

My idea: Two group of nodes: First group labeled as 1..n, second as 1+1000.. n+1000. The connections of Economy-Xpress are edges between nodes 1..n each other, and edges between nodes 1+1000..n+1000 each other. According to problem description, these edges are bi-directional. That means, for this moment doesnt exist connection between first and second group of nodes. Then connections of Commercial-Xpress are special edges, first endpoint is node of first group, and second endpoint is node of second group. These edges are bi-directional too.

That I used Dijkstra with editing of shortest path. The start node is S, the end nodes are two: E or E+1000. Which of this two nodes is earlier in set of visited nodes, that is end node of path. If it is E, that means, that it is not needed to use Ticket, if it is E+1000, that means, that in some node was used the ticket. According to end node, I write the output in required format.

My idea is wrong (at contest 8 WA, now 2 WA), but I cannot find, where can be a mistake. The graph is build so, that at most one edge is used from Commercial-Xpress (if the road gets from group of nodes labeled 1..n to 1+1000..n+1000) and the algorithm surely find shortest path from start to end.

I write blank line after each test case too.

Can anyone help me (find mistake in my idea, describe correct idea, get some I/O, other) ?

Thanks in advance!

(Please sorry for my bad english)

[fpavetic]

Then connections of Commercial-Xpress are special edges, first endpoint is node of first group, and second endpoint is node of second group. These edges are bi-directional too.

i do not think so that you should make special edges bidirectional. just make them directed from the first set to the second. in that way you ensure you do not use Commercial-Xpress edge more that once.

Filip

[jurajz]

Then connections of Commercial-Xpress are special edges, first endpoint is node of first group, and second endpoint is node of second group. These edges are bi-directional too.

i do not think so that you should make special edges bidirectional. just make them directed from the first set to the second. in that way you ensure you do not use Commercial-Xpress edge more that once.

Filip

Thanks for your reply,

I think it so, for example, sample input:

1
2 4 3

means, that there is edge from 2 to 1004 (with weight 3) and from 4 to 1002 too. (So both edges are pointed from 1..n to 1+1000..n+1000) It is wrong? Should it be only from 2 to 1004?

[sohel]

I did an 'exhaustive' bfs for this one with int optimize[501][2];.

- optimize[a][0] means the least cost from source to node a without using any commercial edge and
- optimize[a][1] means the least cost from source to node a by using a commercial edge.

I had trouble in printing the path since a linear parent[] doesn't work. Later I had to maintain the path in the node itself with a vector<int>..

struct node {
int current_node;
int cost_to_reach_this_node;
int have_I_used_commercial ticket; // 0/1
vector<int> v; // the nodes I have visited coming to this node;
int special_edge; // the node from which I have used the commercial ticket .. -1 otherwise
};

[shihabrc]

my idea was to first find the sp from start to all other vertices (say its d0[]) and end to all other vertices( say it is d1[]). then for each edge(u,v) in the commercial express i checked wheather i hav a smaller d0 + w(u,v) + d1[v] lenght(i cheked it for bothe (u,v) and (v,u) ), if a smaller length was found then i updated my current path with start ->u - v->end. Got wa for this.is this method incorrect ?

[sclo]

I did an 'exhaustive' bfs for this one with int optimize[501][2];.

- optimize[a][0] means the least cost from source to node a without using any commercial edge and
- optimize[a][1] means the least cost from source to node a by using a commercial edge.

I had trouble in printing the path since a linear parent[] doesn't work. Later I had to maintain the path in the node itself with a vector<int>..

struct node {
int current_node;
int cost_to_reach_this_node;
int have_I_used_commercial ticket; // 0/1
vector<int> v; // the nodes I have visited coming to this node;
int special_edge; // the node from which I have used the commercial ticket .. -1 otherwise
};

I just maintain previous node information as a pair<int,int>.

[glue2glee]

my idea was to first find the sp from start to all other vertices (say its d0[]) and end to all other vertices( say it is d1[]). then for each edge(u,v) in the commercial express i checked wheather i hav a smaller d0 + w(u,v) + d1[v] lenght(i cheked it for bothe (u,v) and (v,u) ), if a smaller length was found then i updated my current path with start ->u - v->end. Got wa for this.is this method incorrect ?

I tried the same way! It got me WA too! I cannot see my fault either.

[Observer]

Test cases are not generated by me. The only tricky case that I know is that the starting location is the airport.

[kruseborn]

Hi!
Can someone check my in and outdata to see if my answer is right. Been traying to get in data so my program prints something wrong but cant find it.

IN

4 1 4
4
1 2 2
1 3 3
2 4 4
3 4 5
1
2 4 3

4 4 4
4
1 2 2
1 3 3
2 4 4
3 4 5
1
2 4 3

5 1 5
3
1 2 4
2 3 4
3 4 4
5
1 2 2
2 3 2
1 3 2
2 4 2
4 5 10


5 5 1
3
1 2 4
2 3 4
3 4 4
5
1 2 2
2 3 2
1 3 2
2 4 2
4 5 10

7 1 3
4
1 4 2
4 5 2
5 6 2
6 7 2
5
1 2 1
2 3 1
7 3 1
6 7 1
1 6 1

7 7 1
4
1 4 2
4 5 2
5 6 2
6 7 2
5
1 2 1
2 3 1
7 3 1
6 7 1
1 6 1

OUT

1 2 4
2
5

4
Ticket Not Used
0

1 2 3 4 5
4
22

5 4 3 2 1
5
22

1 4 5 6 7 3
7
9

7 6 1
6
3

[Jan]

My accepted code produces same output.

[sclo]

my idea was to first find the sp from start to all other vertices (say its d0[]) and end to all other vertices( say it is d1[]). then for each edge(u,v) in the commercial express i checked wheather i hav a smaller d0 + w(u,v) + d1[v] lenght(i cheked it for bothe (u,v) and (v,u) ), if a smaller length was found then i updated my current path with start ->u - v->end. Got wa for this.is this method incorrect ?

I tried the same way! It got me WA too! I cannot see my fault either.

If you did enough iterations for this method, you would get TLE. So your method is not correct.

[Giorgi]

my idea was to first find the sp from start to all other vertices (say its d0[]) and end to all other vertices( say it is d1[]). then for each edge(u,v) in the commercial express i checked wheather i hav a smaller d0 + w(u,v) + d1[v] lenght(i cheked it for bothe (u,v) and (v,u) ), if a smaller length was found then i updated my current path with start ->u - v->end. Got wa for this.is this method incorrect ?

algorithm is correct , I solved this problem with same algo

[Climber.pI]

this problem don't only have one testdata..
I used SFPA, but I always get RTE.

[tanmoy]

Need some critical cases........

[prashantharshi]

the problem doesnt have the optimal substructure property so how can one use greedy algorithm(dijkstra),
i think we can modify dijkstra algo by keeping track of the minimum distance from both economical and express rails
and then we can find shortest route