UVa 10356

From Algorithmist
Jump to navigation Jump to search

{{subst:Problem}}

UV 10356 - Rough Roads[edit]

Summary[edit]

Dijkstra algorithm

Explanation[edit]

1) Dijkstra algorithm after some adjustment of a graph.
2) Create such a graph that for every junction(vertex) will create a vertex from which is a street taken with a bike taken on his back and another vertex which from is street taken riding a bike
3) Run dijkstra - Dijkstra(start, end) with Dijkstra(V0, Vn-1)
4) Hint: Vertexes(junctions)

                            v(0)...v(n-1) are for vertexes from which is bike taken on his back
                            v(n)...v(2n-1) are for vertexes from which is bike ridden

5) For every path from v(a)<--->v(b) create 4 paths in a graph

                                 v(a)->v(b+n)
                                 v(b+n)->v(a)
                                 v(b)->v(a+n)
                                 v(a+n)->v(b)
                               

Gotchas[edit]

Solution[edit]

import java.util.*;
import java.io.*;

class Main {
	public static void main(String[] args) throws Exception {
		Scanner in = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out, true);
		int set = 0;
		while (in.hasNextInt()) {
			set++;
			out.println("Set #" + set);

			int n = in.nextInt();
			int m = in.nextInt();

			List<Node> nodeList = new ArrayList<Node>();
			for (int i = 0; i < 2 * n; i++) {
				Node node = new Node(i);
				nodeList.add(node);
			}

			for (int i = 0; i < m; i++) {
				int a = in.nextInt();
				int b = in.nextInt();
				int c = in.nextInt();

				Node nodeA = nodeList.get(a);
				Node nodeAN = nodeList.get(a + n);
				Node nodeB = nodeList.get(b);
				Node nodeBN = nodeList.get(b + n);

				Edge e1 = new Edge(nodeA, nodeBN, c);
				Edge e2 = new Edge(nodeBN, nodeA, c);
				Edge e3 = new Edge(nodeAN, nodeB, c);
				Edge e4 = new Edge(nodeB, nodeAN, c);

				nodeA.addEdge(e1);
				nodeBN.addEdge(e2);
				nodeAN.addEdge(e3);
				nodeB.addEdge(e4);
			}

			PriorityQueue<Node> queue = new PriorityQueue<Node>(2*n, new NodeComparator());
			Node startNode = nodeList.get(0);
			startNode.setCurrentCost(0);

			queue.add(startNode);
			for (int i = 1; i < 2 * n; i++) {
				queue.add(nodeList.get(i));
			}

			while (!queue.isEmpty()) {
				Node currentNode = queue.remove();
				List<Edge> edges = currentNode.getEdges();
				for (int i = 0; i < edges.size(); i++) {
					Edge e = edges.get(i);

					Node start = e.getStart();
					Node end = e.getEnd();
					int cost = e.getCost();

					// relaxation
					if (start.getCurrentCost() != -1 && (end.getCurrentCost() == -1 || (end.getCurrentCost() > start.getCurrentCost() + cost))) {
						queue.remove(end);
						end.setCurrentCost(start.getCurrentCost() + cost);
						end.setPreviousNode(start);
						queue.add(end);
					}
				}
			}

			Node target = nodeList.get(n - 1);
			int currentCost = target.getCurrentCost();
			if (currentCost == -1) {
				out.println("?");
			} else {
				out.println(currentCost);
			}
		}

		out.flush();
		out.close();

	}
}

class Edge {
	private Node start;
	private Node end;
	private int cost;

	public Edge(Node start, Node end, int cost) {
		this.start = start;
		this.end = end;
		this.cost = cost;
	}

	public Node getStart() {
		return start;
	}

	public Node getEnd() {
		return end;
	}

	public int getCost() {
		return cost;
	}
}

class Node {
	private int n;
	private List<Edge> edges = new ArrayList<Edge>();

	private int currentCost = -1;
	private Node previousNode;

	public Node(int n) {
		this.n = n;
	}

	public void addEdge(Edge e) {
		edges.add(e);
	}

	public List<Edge> getEdges() {
		return edges;
	}

	public int getCurrentCost() {
		return currentCost;
	}

	public void setCurrentCost(int currentCost) {
		this.currentCost = currentCost;
	}

	public Node getPreviousNode() {
		return previousNode;
	}

	public void setPreviousNode(Node previousNode) {
		this.previousNode = previousNode;
	}

	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + n;
		return result;
	}

	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		Node other = (Node) obj;
		if (n != other.n)
			return false;
		return true;
	}

}

class NodeComparator implements Comparator<Node> {

	public int compare(Node o1, Node o2) {
		if (o1.getCurrentCost() == o2.getCurrentCost()) {
			return 0;
		} else if (o1.getCurrentCost() == -1) {
			return 1;
		} else if (o2.getCurrentCost() == -1) {
			return -1;
		} else if (o1.getCurrentCost() < o2.getCurrentCost()) {
			return -1;
		} else if (o1.getCurrentCost() > o2.getCurrentCost()) {
			return 1;
		}
		return 0;
	}

}

References[edit]

  1. Reference 1

Categories here, use the form [[Category:UVa Online Judge|10356]] [[Category: Category Name]], see Categories for a list