11374 - Airport Express

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

Moderator: Board moderators

jurajz
Learning poster
Posts: 69
Joined: Sat Sep 02, 2006 7:30 pm
Location: Slovakia

11374 - Airport Express

Post by jurajz » Sun Dec 30, 2007 1:17 pm

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
Learning poster
Posts: 51
Joined: Sat Mar 04, 2006 8:00 pm

Post by fpavetic » Sun Dec 30, 2007 1:28 pm

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
Learning poster
Posts: 69
Joined: Sat Sep 02, 2006 7:30 pm
Location: Slovakia

Post by jurajz » Sun Dec 30, 2007 1:57 pm

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?

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Sun Dec 30, 2007 2:02 pm

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
New poster
Posts: 49
Joined: Sun Sep 18, 2005 10:20 am
Location: CSE,BUET
Contact:

Post by shihabrc » Sun Dec 30, 2007 3:07 pm

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 ?
Shihab
CSE,BUET

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Mon Dec 31, 2007 7:37 am

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>.

glue2glee
New poster
Posts: 1
Joined: Sun Dec 30, 2007 7:06 pm

Post by glue2glee » Mon Dec 31, 2007 10:36 am

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.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Mon Dec 31, 2007 11:08 am

Test cases are not generated by me. The only tricky case that I know is that the starting location is the airport.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

kruseborn
New poster
Posts: 1
Joined: Thu Jan 03, 2008 12:55 am
Location: Stockholm

Post by kruseborn » Thu Jan 03, 2008 4:05 pm

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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Thu Jan 03, 2008 8:53 pm

My accepted code produces same output.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Fri Jan 04, 2008 12:05 am

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.

Giorgi
New poster
Posts: 48
Joined: Wed Jun 07, 2006 6:26 pm
Location: Georgia Tbilisi

Post by Giorgi » Sat Jan 05, 2008 1:02 am

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

Climber.pI
New poster
Posts: 1
Joined: Sun Feb 07, 2010 3:49 pm

Re: 11374 - Airport Express

Post by Climber.pI » Wed Dec 15, 2010 2:58 pm

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

tanmoy
New poster
Posts: 18
Joined: Wed Jun 25, 2008 2:25 pm

Re: 11374 - Airport Express

Post by tanmoy » Mon Jan 17, 2011 8:38 pm

Need some critical cases........ :D

prashantharshi
New poster
Posts: 22
Joined: Wed May 21, 2014 10:16 am

Re: 11374 - Airport Express

Post by prashantharshi » Sun Jun 08, 2014 2:01 pm

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

Post Reply

Return to “Volume 113 (11300-11399)”