Page 1 of 2

11374 - Airport Express

Posted: Sun Dec 30, 2007 1:17 pm
by 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)

Posted: Sun Dec 30, 2007 1:28 pm
by 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

Posted: Sun Dec 30, 2007 1:57 pm
by jurajz
fpavetic wrote:
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?

Posted: Sun Dec 30, 2007 2:02 pm
by 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
};

Posted: Sun Dec 30, 2007 3:07 pm
by 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 ?

Posted: Mon Dec 31, 2007 7:37 am
by sclo
sohel wrote: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>.

Posted: Mon Dec 31, 2007 10:36 am
by glue2glee
shihabrc wrote: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.

Posted: Mon Dec 31, 2007 11:08 am
by Observer
Test cases are not generated by me. The only tricky case that I know is that the starting location is the airport.

Posted: Thu Jan 03, 2008 4:05 pm
by 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

Posted: Thu Jan 03, 2008 8:53 pm
by Jan
My accepted code produces same output.

Posted: Fri Jan 04, 2008 12:05 am
by sclo
glue2glee wrote:
shihabrc wrote: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.

Posted: Sat Jan 05, 2008 1:02 am
by Giorgi
shihabrc wrote: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

Re: 11374 - Airport Express

Posted: Wed Dec 15, 2010 2:58 pm
by Climber.pI
this problem don't only have one testdata..
I used SFPA, but I always get RTE.

Re: 11374 - Airport Express

Posted: Mon Jan 17, 2011 8:38 pm
by tanmoy
Need some critical cases........ :D

Re: 11374 - Airport Express

Posted: Sun Jun 08, 2014 2:01 pm
by 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