Archive for the ‘Dijkstra’ Category

UVA – 11338 – Minefield   Leave a comment


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Minefield {
	static class Pair<T1, T2> implements Comparable<Pair<T1, T2>> {
		T1 first;
		T2 second;

		public Pair(T1 f, T2 s) {
			first = f;
			second = s;
		}

		public T1 getFirst() {
			return first;
		}

		public T2 getSecond() {
			return second;
		}

		public String toString() {
			return "(" + first + "," + second + ")";
		}

		@Override
		public int compareTo(Pair<T1, T2> o) {
			return ((Comparable) second).compareTo(o.second);
		}

	}

	public static void main(String[] args) throws Exception {
		InputReader in = new InputReader(System.in);
		while (true) {
			String s = in.next();
			if (s.equals("*"))
				break;
			int w = Integer.parseInt(s);
			int h = in.nextInt();
			int n = in.nextInt();
			double[] x = new double[n + 2];
			double[] y = new double[n + 2];
			x[0] = 0;
			y[0] = 0;
			x[n + 1] = w;
			y[n + 1] = h;
			for (int i = 1; i <= n; i++) {
				x[i] = in.nextDouble();
				y[i] = in.nextDouble();
			}
			double max = in.nextDouble();
			PriorityQueue<Pair<Integer, Double>> Q = new PriorityQueue<Pair<Integer, Double>>();
			boolean[] v = new boolean[n + 2];
			double[] dist = new double[n + 2];
			Arrays.fill(dist, 1e9);
			dist[0] = 0.0;
			Q.add(new Pair<Integer, Double>(0, 0.0));
			boolean found = false;
			while (!Q.isEmpty() && !found) {
				Pair<Integer, Double> p = Q.remove();
				int i = p.first;
				if (!v[p.getFirst()] && p.getSecond() < max + 1e-8) {
					v[p.getFirst()] = true;
					if (p.getFirst() == n + 1)
						found = true;
					for (int j = 1; j <= n + 1; j++) {
						if ((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j])
								* (y[i] - y[j]) < 1.5 * 1.5 + 1e-8
								&& dist[i]
										+ Math.sqrt((x[i] - x[j])
												* (x[i] - x[j]) + (y[i] - y[j])
												* (y[i] - y[j])) < dist[j]) {
							dist[j] = dist[i]
									+ Math.sqrt((x[i] - x[j]) * (x[i] - x[j])
											+ (y[i] - y[j]) * (y[i] - y[j]));
							Q.add(new Pair<Integer, Double>(j, dist[j]));
						}
					}
				} else if (p.getSecond() > max)
					break;
			}
			if (found)
				System.out.println("I am lucky!");
			else
				System.out.println("Boom!");
		}
	}

	static class InputReader {
		private BufferedReader reader;
		private StringTokenizer tokenizer;

		public InputReader(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream));
			tokenizer = null;
		}

		public String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}

		public double nextDouble() {
			return Double.parseDouble(next());
		}
	}
}

Advertisements

Posted July 5, 2012 by epicrado in Dijkstra

UVA – 11813 – Shopping   Leave a comment


The main idea is to compress the graph so that it only includes nodes with shops and house and fix edges between them as shortest paths using Dijkstra then run the classical TSP

import java.awt.Point;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Shopping {
	static class Path implements Comparable<Path> {
		int x, y;

		public Path(int xx, int yy) {
			x = xx;
			y = yy;
		}

		@Override
		public int compareTo(Path arg0) {
			return y - arg0.y;
		}

	}

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int tc = in.nextInt();
		while (tc-- > 0) {
			int n = in.nextInt();
			int m = in.nextInt();
			LinkedList<Point>[] G = new LinkedList[n];
			for (int i = 0; i < G.length; i++)
				G[i] = new LinkedList<Point>();
			for (int i = 0; i < m; i++) {
				int s = in.nextInt();
				int t = in.nextInt();
				int b = in.nextInt();
				G[s].add(new Point(t, b));
				G[t].add(new Point(s, b));
			}
			int[] special = new int[in.nextInt() + 1];
			int[][] g = new int[special.length][special.length];
			special[0] = 0;
			for (int i = 1; i < special.length; i++)
				special[i] = in.nextInt();
			for (int i = 0; i < special.length; i++) {
				// Starting at the house and every shop complete dijkstra
				int[] dist = new int[n];
				Arrays.fill(dist, 1 << 30);
				PriorityQueue<Path> Q = new PriorityQueue<Path>();
				dist[special[i]] = 0;
				Q.add(new Path(special[i], 0));
				while (!Q.isEmpty()) {
					Path cn = Q.poll();
					if (cn.y == dist[cn.x]) {
						for (Point j : G[cn.x]) {
							if (dist[cn.x] + j.y < dist[j.x]) {
								dist[j.x] = dist[cn.x] + j.y;
								Q.add(new Path(j.x, dist[j.x]));
							}
						}
					}
				}
				for (int j = 0; j < special.length; j++) {
					g[i][j] = dist[special[j]];
				}
			}
			int[][] dp = new int[1 << special.length][special.length];
			// TSP
			for (int i = 0; i < special.length; i++)
				dp[(1 << special.length) - 1][i] = g[i][0];
			for (int i = (1 << special.length) - 2; i >= 0; i--) {
				for (int j = 0; j < special.length; j++) {
					if ((i & (1 << j)) != 0) {
						dp[i][j] = Integer.MAX_VALUE;
						for (int k = 0; k < special.length; k++) {
							if ((i & (1 << k)) == 0) {
								dp[i][j] = Math.min(dp[i][j], g[j][k]
										+ dp[i | (1 << k)][k]);
							}
						}
					}
				}
			}
			System.out.println(dp[1][0]);
		}
	}
}

Posted February 4, 2012 by epicrado in Dijkstra, Dynamic programming

UVA – 10603 – Fill   Leave a comment


import java.util.HashMap;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Scanner;

public class FILL {
	static int inf = 1 << 25;
	static int min(int a, int b) {
		return (a < b) ? a : b;
	}
	static class jugs implements Comparable<jugs> {
		int[] conf, max;
		int poured;
		public String toString() {
			return conf[0] + "/" + max[0] + " " + conf[1] + "/" + max[1] + " "
					+ conf[2] + "/" + max[2];
		}
		public jugs(int a, int b, int c) {
			conf = new int[3];
			max = new int[3];
			conf[0] = conf[1] = 0;
			conf[2] = c;
			max[0] = a;
			max[1] = b;
			max[2] = c;
			poured = 0;
		}
		public int compare(int n) {
			int min = inf;
			for (int i = 0; i < 3; i++) {
				if (conf[i] <= n)
					min = min(n - conf[i], min);
			}
			return min;
		}
		private jugs(jugs x) {
			conf = x.conf.clone();
			max = x.max.clone();
			poured = x.poured;
		}
		public boolean equals(Object o) {
			jugs x = (jugs) o;
			for (int i = 0; i < 3; i++)
				if (conf[i] != x.conf[i])
					return false;
			return true;
		}
		public boolean shouldPour(int a, int b) {
			return a != b && max[b] != conf[b] && conf[a] != 0;
		}
		public int hashCode() {
			int hash = 1;
			hash = hash * 17 + conf[0];
			hash = hash * 31 + conf[1];
			hash = hash * 13 + conf[2];
			return hash;
		}
		public jugs pour(int i, int d) {
			jugs b = new jugs(this);
			int p = min(max[d] - conf[d], conf[i]);
			b.conf[i] -= p;
			b.conf[d] += p;
			b.poured += p;
			return b;
		}
		public int compareTo(jugs o) {
			return poured - o.poured;
		}
	}

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int cases = in.nextInt();
		while (cases-- > 0) {
			int a, b, c, d;
			HashMap<jugs, Integer> dist = new HashMap<jugs, Integer>();
			HashSet<jugs> V = new HashSet<jugs>();
			PriorityQueue<jugs> Q = new PriorityQueue<jugs>();
			a = in.nextInt();
			b = in.nextInt();
			c = in.nextInt();
			d = in.nextInt();
			Q.add(new jugs(a, b, c));
			int minD = inf;
			int bestPour = -1;
			while (!Q.isEmpty()) {
				jugs current = Q.poll();
				if (!V.contains(current)) {
					V.add(current);
					int distance = current.compare(d);
					if (distance < minD) {
						minD = distance;
						bestPour = current.poured;
					}
					if (distance == 0)
						break;
					for (int i = 0; i < 3; i++)
						for (int j = 0; j < 3; j++)
							if (current.shouldPour(i, j)) {
								jugs res = current.pour(i, j);
								if (!dist.containsKey(res)
										|| dist.get(res) < res.poured) {
									dist.put(res, res.poured);
									Q.add(res);
								}
							}
				}
			}
			System.out.println(bestPour + " " + (d - minD));

		}
	}
}

Posted August 29, 2011 by epicrado in Dijkstra

UVA – 10278 – Fire Station   Leave a comment


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Firestation {
	static int inf = 1 << 25;

	static class Edge {
		int t, w;
		public Edge(int tt, int ww) {
			t = tt;
			w = ww;
		}
	}
	static class Node implements Comparable<Node> {
		int n, d;
		public Node(int nn, int ww) {
			n = nn;
			d = ww;
		}
		public int compareTo(Node o) {
			return d - o.d;
		}
	}
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(
				System.in));
		int cases = Integer.parseInt(read.readLine());
		read.readLine();
		while (cases-- > 0) {
			int f, n;
			f = 0;
			n = 0;
			String inp = read.readLine();
			int i;
			for (i = 0; inp.charAt(i) != ' '; i++)
				f = f * 10 + inp.charAt(i) - '0';
			i++;
			for (; i < inp.length(); i++)
				n = n * 10 + inp.charAt(i) - '0';
			int[] dist = new int[n + 1];
			for (i = 1; i <= n; i++)
				dist[i] = inf;
			while (f-- > 0) {
				int c = Integer.parseInt(read.readLine());
				dist[c] = 0;
			}
			LinkedList<Edge>[] G = new LinkedList[n + 1];
			while (read.ready()) {
				inp = read.readLine();
				if (inp.equals(""))
					break;
				int a = 0, b = 0, c = 0;
				for (i = 0; inp.charAt(i) != ' '; i++)
					a = a * 10 + inp.charAt(i) - '0';
				i++;
				for (; inp.charAt(i) != ' '; i++)
					b = b * 10 + inp.charAt(i) - '0';
				i++;
				for (; i < inp.length() && inp.charAt(i) != ' '; i++)
					c = c * 10 + inp.charAt(i) - '0';
				if (G[a] == null)
					G[a] = new LinkedList<Edge>();
				if (G[b] == null)
					G[b] = new LinkedList<Edge>();
				G[a].add(new Edge(b, c));
				G[b].add(new Edge(a, c));
			}

			int min = -1;
			int minimax = -1;
			for (i = 1; i < dist.length; i++) {
				PriorityQueue<Node> Q = new PriorityQueue<Node>();
				for (int j = 1; j < dist.length; j++)
					if (dist[j] == 0)
						Q.add(new Node(j, 0));
				Q.add(new Node(i, 0));
				boolean[] V = new boolean[n + 1];
				int[] cdist = dist.clone();
				cdist[i] = 0;
				while (!Q.isEmpty()) {
					Node current = Q.poll();
					if (!V[current.n]) {
						V[current.n] = true;
						if (G[current.n] != null) {
							for (Edge e : G[current.n]) {
								if (current.d + e.w < cdist[e.t]) {
									cdist[e.t] = current.d + e.w;
									Q.add(new Node(e.t, cdist[e.t]));
								}
							}
						}
					}
				}
				int max = cdist[1];
				for (int k = 2; k < cdist.length; k++)
					if (cdist[k] > max)
						max = cdist[k];
				if (min == -1 || max < minimax) {
					minimax = max;
					min = i;
				}
			}
			System.out.println(min);
			if (cases != 0) {
				System.out.println();
			}
		}
	}
}

Posted August 29, 2011 by epicrado in Dijkstra

UVA – 929 – Number Maze   Leave a comment


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;

public class NumberMaze {
	static int[][] maze = new int[1000][1000];
	static int[][] cost = new int[1000][1000];
	static int inf = 1 << 25;
	static boolean[][] vis = new boolean[1000][1000];
	static int[] dx = { 0, 0, -1, 1 };
	static int[] dy = { -1, 1, 0, 0 };
	static int r, col;

	static class node implements Comparable<node> {
		int i, j, c;

		public node(int i, int j, int c) {
			this.i = i;
			this.j = j;
			this.c = c;
		}

		public int compareTo(node arg0) {
			return c - arg0.c;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int cases = Integer.parseInt(in.readLine());
		int res;
		while (cases-- > 0) {
			r = Integer.parseInt(in.readLine());
			col = Integer.parseInt(in.readLine());
			for (int i = 0; i < r; i++) {
				String inp = in.readLine();
				int last = -1;
				for (int j = 0; j < col; j++) {
					last++;
					res = 0;
					for (; last < inp.length() && inp.charAt(last) != ' '; last++)
						res = res * 10 + inp.charAt(last) - '0';
					maze[i][j] = res;
					vis[i][j] = false;
					cost[i][j] = inf;
				}
			}
			node s = new node(0, 0, maze[0][0]);
			int ei = r - 1;
			int ej = col - 1;
			PriorityQueue<node> Q = new PriorityQueue<node>();
			Q.add(s);
			while (!Q.isEmpty()) {
				node c = Q.poll();
				if (c.i == ei && c.j == ej) {
					System.out.println(c.c);
					break;
				} else if (!vis[c.i][c.j]) {
					vis[c.i][c.j] = true;
					for (int i = 0; i < 4; i++) {
						int ni = c.i + dx[i];
						int nj = c.j + dy[i];
						if (ni >= 0 && ni < r && nj >= 0 && nj < col
								&& c.c + maze[ni][nj] < cost[ni][nj]) {
							Q.add(new node(ni, nj, c.c + maze[ni][nj]));
							cost[ni][nj] = c.c + maze[ni][nj];
						}
					}
				}
			}
		}
	}
}

Posted August 29, 2011 by epicrado in Dijkstra

UVA – 341 – Non-Stop Travel   1 comment


import java.util.Arrays;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.Stack;

public class NonStopTravel {
	static class Edge {
		int t, w;

		public Edge(int tt, int ww) {
			t = tt;
			w = ww;
		}

		public String toString() {
			return "(" + t + " " + w + ")";
		}
	}

	static class node implements Comparable<node> {
		int i, p;

		public node(int ii, int pp) {
			i = ii;
			p = pp;
		}

		@Override
		public int compareTo(node o) {
			return p - o.p;
		}

	}

	public static void printPath(LinkedList<Edge>[] G, int s, int t, int c) {
		int[] parents = new int[G.length];
		int[] d = new int[G.length];
		boolean[] v = new boolean[G.length];
		Arrays.fill(d, 1 << 20);
		d[s] = 0;
		PriorityQueue<node> Q = new PriorityQueue<node>();
		Q.add(new node(s, 0));
		while (!Q.isEmpty()) {
			node n = Q.poll();
			if (!v[n.i]) {
				v[n.i] = true;
				if (G[n.i] != null) {
					for (Edge e : G[n.i]) {
						if (e.w + d[n.i] < d[e.t]) {
							d[e.t] = e.w + d[n.i];
							Q.add(new node(e.t, d[e.t]));
							parents[e.t] = n.i;
						}
					}
				}
			}
		}
		Stack<Integer> flip = new Stack<Integer>();
		int k = t;
		while (k != 0) {
			flip.add(k);
			k = parents[k];
		}
		System.out.printf("Case %d: Path =", c);
		while (!flip.isEmpty())
			System.out.printf(" %d", flip.pop());
		System.out.printf("; %d second delay\n", d[t]);

	}

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int nodes = in.nextInt();
		int c = 1;
		while (nodes != 0) {
			LinkedList<Edge>[] G = new LinkedList[nodes + 1];
			for (int i = 1; i <= nodes; i++) {
				int z = in.nextInt();
				if (z != 0)
					G[i] = new LinkedList<Edge>();
				while (z-- > 0) {
					int v = in.nextInt();
					int w = in.nextInt();
					G[i].add(new Edge(v, w));
				}
			}
			int from = in.nextInt();
			int to = in.nextInt();
			printPath(G, from, to, c++);
			nodes = in.nextInt();
		}
	}
}

Posted August 10, 2011 by epicrado in Dijkstra

UVA – 10986 – Sending email   Leave a comment


import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Scanner;

public class SendingEmail {

	static class Edge {
		int t, w;

		public Edge(int tt, int ww) {
			t = tt;
			w = ww;
		}

	}

	static class Node implements Comparable<Node> {
		int d, i;

		Node(int ii, int dd) {
			i = ii;
			d = dd;
		}

		@Override
		public int compareTo(Node o) {
			return d - o.d;
		}

	}

	public static int shortest(LinkedList<Edge>[] g, int s, int t) {
		int[] d = new int[g.length];
		Arrays.fill(d, 1 << 30);
		boolean[] v = new boolean[g.length];
		PriorityQueue<Node> Q = new PriorityQueue<Node>();
		Q.add(new Node(s, 0));
		d[s] = 0;
		while (!Q.isEmpty()) {
			Node c = Q.poll();
			if (c.i == t)
				return c.d;
			else if (!v[c.i]) {
				v[c.i] = true;
				if (g[c.i] != null) {
					for (Edge e : g[c.i]) {
						if (e.w + d[c.i] < d[e.t]) {
							d[e.t] = e.w + d[c.i];
							Q.add(new Node(e.t, d[e.t]));
						}
					}
				}
			}
		}
		return -1;
	}

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int c = in.nextInt();
		for (int i = 1; i <= c; i++) {
			int n, m, s, t;
			n = in.nextInt();
			m = in.nextInt();
			s = in.nextInt();
			t = in.nextInt();
			LinkedList<Edge>[] G = new LinkedList[n];
			while (m-- > 0) {
				int from = in.nextInt();
				int to = in.nextInt();
				int w = in.nextInt();
				if (G[from] == null) {
					G[from] = new LinkedList<Edge>();
				}
				if (G[to] == null) {
					G[to] = new LinkedList<Edge>();
				}
				G[from].add(new Edge(to, w));
				G[to].add(new Edge(from, w));
			}
			int res = shortest(G, s, t);
			if (res == -1)
				System.out.printf("Case #%d: unreachable\n", i);
			else
				System.out.printf("Case #%d: %d\n", i, res);
		}
	}
}

Posted August 10, 2011 by epicrado in Dijkstra