Problemin təsviri:
The local commuter railroad services a number of towns in Azerbaijan. Because of monetary concerns, all of the tracks are ‘one-way.’ That is, a route from A to B does not imply the existence of a route from B to A.
In fact, even if both of these routes do happen to exist, they are distinct and are not necessarily the same distance!
The purpose of this problem is to help the railroad provide its customers with information about the routes.
In particular, you will compute the
- distance along a certain route,
- the number of different routes between two towns,
- and the shortest route between two towns.
Input: A directed graph where a node represents a town and an edge represents a route between two towns. The weighting of the edge represents the distance between the two towns. A given route will never appear more than once, and for a given route, the starting and ending town will not be the same town.
Output: For test input 1 through 5, if no such route exists, output 'NO SUCH ROUTE'. Otherwise, follow the route as given; do not make any extra stops! For example, the first problem means to start at city A, then travel directly to city B (a distance of 5), then directly to city C (a distance of 4).
1. The distance of the route A-B-C.
2. The distance of the route A-D.
3. The distance of the route A-D-C.
4. The distance of the route A-E-B-C-D.
5. The distance of the route A-E-D.
6. The number of trips starting at C and ending at C with a maximum of 3 stops. In the sample data below, there are two such trips: C-D-C (2 stops) and C-E-B-C (3 stops).
7. The number of trips starting at A and ending at C with exactly 4 stops. In the sample data below, there are three such trips: A to C (via B, C, D); A to C (via D, C, D);
and A to C (via D, E, B).
8. The length of the shortest route (in terms of distance to travel) from A to C.
9. The length of the shortest route (in terms of distance to travel) from B to B.
10.The number of different routes from C to C with a distance of less than 30. In the sample data, the trips are:
CDC, CEBC, CEBCDC, CDCEBC, CDEBC, CEBCEBC, CEBCEBCEBC.
Test Input:
For the test input, the towns are named using the first few letters of the alphabet from A to E. A route between two towns (A to B) with a distance of 5 is represented as AB5.
Graph: AB5, BC4, CD8, DC8, DE6, AD5, CE2, EB3, AE7
Expected Output:
Output #1: 9
Output #2: 5
Output #3: 13
Output #4: 22
Output #5: NO SUCH ROUTE
Output #6: 2
Output #7: 3
Output #8: 9
Output #9: 9
Output #10: 7
Problemin həlli:
Kod strukturu:
Edge.java
package az.mm.graph; /** * * @author MM <[email protected]> */ public class Edge { private final int from; private final int to; private final int weight; public Edge(int from, int to, int weight) { if (from < 0) throw new IllegalArgumentException("Vertex names must be positive Integer"); if (to < 0) throw new IllegalArgumentException("Vertex names must be positive Integer"); if (weight < 0) throw new IllegalArgumentException("Weight must be positive"); this.from = from; this.to = to; this.weight = weight; } public int from() { return from; } public int to() { return to; } public int weight() { return weight; } }
Graph.java
package az.mm.graph; import java.util.ArrayList; import java.util.Arrays; import java.util.LinkedList; import java.util.List; import java.util.function.Predicate; /** * * @author MM <[email protected]> */ public class Graph { private static final String[] VERTEX_LIST = {"A", "B", "C", "D", "E"}; private final List<Edge>[] adj; private List<String> allPath; private int to; private int maxDistance; private int stops; private int routesCount; private int tripsCount; private Graph(int n) { if (n < 0) throw new IllegalArgumentException("Number of vertices in a Graph must be positive"); adj = (LinkedList<Edge>[]) new LinkedList[n]; for (int i = 0; i < n; i++) adj[i] = new LinkedList<>(); } public Graph(String inputGraph) { this(VERTEX_LIST.length); initializeGraph(inputGraph); } private void initializeGraph(String inputGraph){ String[] inputArr = inputGraph.split(","); for (String s : inputArr) { s = s.trim(); int from = getIndex(s.substring(0, 1)); int to = getIndex(s.substring(1, 2)); int weight = Integer.parseInt(s.substring(2)); Edge e = new Edge(from, to, weight); addEdge(e); } } private void addEdge(Edge e) { int v = e.from(); adj[v].add(e); } private List<Edge> adj(int v) { if (v < 0 || v >= VERTEX_LIST.length) throw new IndexOutOfBoundsException("vertex " + v + " not exists"); return adj[v]; } public String displayDistance(String route){ int distance = calculateDistance(route); return (distance != -1) ? String.valueOf(distance) : "NO SUCH ROUTE"; } private int calculateDistance(String route){ if(route == null) throw new IllegalArgumentException("Route is wrong"); int distance = 0; String[] vertex = route.trim().split(""); int from, to; for (int i = 0; i < vertex.length-1;) { boolean hasPath = false; from = getIndex(vertex[i++]); to = getIndex(vertex[i]); List<Edge> edgeList = adj(from); for (Edge edge : edgeList) if (edge.to() == to) { distance += edge.weight(); hasPath = true; break; } if(!hasPath) return -1; } return distance; } public int calculateTripsCount(String from, String to, Predicate<Integer> p, int stops){ this.to = getIndex(to); this.stops = stops; this.tripsCount = 0; int startIndex = getIndex(from); calculateTripsCount(startIndex, String.valueOf(startIndex), p); return tripsCount; } private void calculateTripsCount(int from, String path, Predicate<Integer> p) { List<Edge> edges = adj(from); for (Edge e: edges) { String next = path + e.to(); int stopCount = next.length()-1; if (this.to == e.to() && p.test(stopCount)) tripsCount++; if(stopCount <= stops) calculateTripsCount(e.to(), next, p); } } public int calculateShortestPath(String from, String to){ allPath = new ArrayList<>(); this.to = getIndex(to); int startIndex = getIndex(from); calculateShortestPath(startIndex, String.valueOf(startIndex)); int shortestDistance = Integer.MAX_VALUE, currentDistance; for(String s: allPath){ currentDistance = calculateDistance(s); if(shortestDistance > currentDistance) shortestDistance = currentDistance; } if(shortestDistance == Integer.MAX_VALUE) return 0; return shortestDistance; } private void calculateShortestPath(int from, String path) { List<Edge> edges = adj(from); for (Edge e: edges) { if (path.length()>1 && path.substring(1).contains(String.valueOf(e.to()))) //checked visited or not continue; String next = path + e.to(); if (this.to == e.to()) allPath.add(getPathName(next)); calculateShortestPath(e.to(), next); } } public int calculateRoutesCount(String from, String to, int maxDistance){ this.to = getIndex(to); this.maxDistance = maxDistance; this.routesCount = 0; int startIndex = getIndex(from); calculateRoutesCount(startIndex, String.valueOf(startIndex)); return routesCount; } private void calculateRoutesCount(int from, String path) { List<Edge> edges = adj(from); for (Edge e: edges) { String next = path + e.to(); int distance = calculateDistance(getPathName(next)); if (this.to == e.to() && (distance < maxDistance)) routesCount++; if(distance < maxDistance) calculateRoutesCount(e.to(), next); } } private static int getIndex(String vertex) { int index = Arrays.binarySearch(VERTEX_LIST, vertex); if (index < 0) throw new IllegalArgumentException("Wrong input"); return index; } private String getVertexName(int index) { if (index < 0 || index >= VERTEX_LIST.length) throw new IllegalArgumentException("Wrong index"); return VERTEX_LIST[index]; } private String getPathName(String path){ String arr[] = path.trim().split(""); String name = ""; for(String v: arr) name += getVertexName(Integer.parseInt(v)); return name; } }
Main.java
package az.mm.graph; /** * Compilation: javac Main.java * Execution: java Main "AB5, BC4, CD8, DC8, DE6, AD5, CE2, EB3, AE7" * * @author MM <[email protected]> */ public class Main { public static void main(String[] args) { parser(args); Graph g = new Graph(args[0]); System.out.println("Output #1: " + g.displayDistance("ABC")); System.out.println("Output #2: " + g.displayDistance("AD")); System.out.println("Output #3: " + g.displayDistance("ADC")); System.out.println("Output #4: " + g.displayDistance("AEBCD")); System.out.println("Output #5: " + g.displayDistance("AED")); System.out.println("Output #6: " + g.calculateTripsCount("C", "C", t -> t <= 3, 3)); System.out.println("Output #7: " + g.calculateTripsCount("A", "C", t -> t == 4, 4)); System.out.println("Output #8: " + g.calculateShortestPath("A", "C")); System.out.println("Output #9: " + g.calculateShortestPath("B", "B")); System.out.println("Output #10: " + g.calculateRoutesCount("C", "C", 30)); } private static void parser(String... args){ String sample = " Provide input same as (quotes is important): \"AB5, BC4, CD8, DC8, DE6, AD5, CE2, EB3, AE7\""; if(args.length != 1) throw new IllegalArgumentException("Wrong input length!" + sample); String arr[] = args[0].split(","); for(String s: arr){ s = s.trim(); if(s.length() < 3) throw new IllegalArgumentException("Wrong input context!" + sample); if(!s.substring(2).matches("-?\\d+")) throw new IllegalArgumentException("Wrong edge distance!" + sample); } } }
Github linki:
