Rhobincu: Pagină nouă: = GPS = Little John was promoted to Senior Software Engineer. His first project is to write an engine for a next generation GPS device. What he has to do is to implement an algorithm...

2014-05-11T18:23:46Z

Pagină nouă: = GPS = Little John was promoted to Senior Software Engineer. His first project is to write an engine for a next generation GPS device. What he has to do is to implement an algorithm...

Pagină nouă

= GPS =

Little John was promoted to Senior Software Engineer. His first project is to write an engine for a next generation GPS device. What he has to do is to implement an algorithm to find the shortest route from the starting point to the destination. The map has already been translated and is represented as a graph where intersections are nodes, and streets and edges. Since some streets are only one-way, this graph is an oriented graph.

Help Little John write this program.

== Requirement ==

Given an oriented graph, find the shortest path between the source node and the destination node.

== Input Data ==

A file called ''gps.in'', containing the number of intersections N on the first line, and N x N subsequent values, defining the adjacency matrix, arranged in a square, on N lines. A value of -1 in the adjacency means that there is no route between those nodes. The last line contains the starting node and the destination node.

== Output Data ==

A file called ''gps.out'', containing the cost of the shortest route (or -1 if there is none) on the first line and the path itself on the second line (the second line is missing if there is no route).

== Restrictions ==
1 ≤ N ≤ 1000

== Examples ==

{| class="wikitable"
|- bgcolor="#ddeeff" align="left"
|'''Input''' || '''Output'''
|- bgcolor="#ddffdd" align="left"
|
<pre style="font-size:12px">
7
0 -1 1 1 -1 2 -1
3 0 1 -1 -1 -1 -1
-1 2 0 -1 2 -1 -1
-1 -1 -1 0 5 -1 2
-1 -1 2 5 0 -1 -1
-1 -1 -1 -1 -1 0 2
-1 -1 -1 -1 1 -1 0
5 0
</pre>
|
<pre style="font-size:12px">
10
5 6 4 2 1 0
</pre>
|- bgcolor="#ddffdd" align="left"
|<pre style="font-size:12px">
7
0 -1 1 1 -1 2 -1
3 0 1 -1 -1 -1 -1
-1 2 0 -1 2 -1 -1
-1 -1 -1 0 5 -1 2
-1 -1 -1 5 0 -1 -1
-1 -1 -1 -1 -1 0 2
-1 -1 -1 -1 1 -1 0
5 0
</pre>
|
<pre style="font-size:12px">
-1
</pre>
|}

DSA Homework 6 - Revizia istoricului

Rhobincu: Pagină nouă: = GPS = Little John was promoted to Senior Software Engineer. His first project is to write an engine for a next generation GPS device. What he has to do is to implement an algorithm...