### 11374 - Airport Express

Posted:

**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)

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)