Category Archives: Dijkstra

USACO 3.2.6 – Sweet Butter

#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
struct E { int b, d; };
int main() {
	freopen("butter.in", "r", stdin), freopen("butter.out", "w", stdout);
	int N, C, P, p[801] = { 0 }, best[801], INF = 10000000, min_r = INF;
	vector<E> e[801]; vector<int> cows;
	fill(e, e + 800, vector<E> ()), fill(best, best + 801, INF);
	scanf("%d %d %d", &N, &P, &C);
	for (int c, i = 0; i < N; p[c]++, cows.push_back(c), i++)
		scanf("%d", &c);
	for (int a, b, d, c = 0; c < C; c++) {
		scanf("%d %d %d", &a, &b, &d);
		e[a].push_back(E { b, d }), e[b].push_back(E { a, d });
	}
	for (int s = 1, r = 0; s <= P; fill(best, best + 801, INF), r = 0, ++s) {
		queue<E> q; q.push(E { s, best[s] = 0 });
		while (q.size()) {
			E f = q.front(); q.pop();
			for (int b = 0; b < e[f.b].size(); ++b) {
				E o = e[f.b][b];
				if (best[o.b] > o.d + best[f.b])
					q.push(E { o.b, (best[o.b] = o.d + best[f.b]) });
			}
		}
		for (int i = 0; i < cows.size(); ++i)
			r += best[cows[i]];
		min_r = r < min_r ? r : min_r;
	}
	printf("%d\n", min_r);
}
Advertisements

USACO 2.4.4 – Bessie Come Home



#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
struct N{
	int n, d;
};
bool operator<(const N& a, const N& b){
	return a.d<b.d;
}
int main() {

	freopen("comehome.in", "r", stdin), freopen("comehome.out", "w", stdout);
	char c1, c2;
	int n, di, g[300][300] ={{0}}, d[300]={0}, INF=1<<30;
	fill(d, d+299, INF);
	priority_queue<N> q;
	scanf("%d\n", &n);
	for (int i = 0; i < n; i++, getchar()) {
		scanf("%c %c %d", &c1, &c2 , &di);
		g[c1][c2] = g[c2][c1] = min(di, g[c1][c2]?g[c1][c2]:INF);
	}
	N best{'Z', INF};
	q.push(N{'Z', d['Z']=0});
	while(q.size()){
		N n = q.top();  q.pop();
		if(n.n>='A' && n.n<'Z' && n.d<best.d) best =  n;
 		for(int b='A'; b<'Z'; b++)
			if(g[n.n][b] && d[b] >d[n.n]+g[n.n][b])	q.push(N{b, d[b]=d[n.n]+g[n.n][b]});
		for(int b='a'; b<='z'; b++)
			if(g[n.n][b] && d[b] >d[n.n]+g[n.n][b])	q.push(N{b, d[b]=d[n.n]+g[n.n][b]});
	}

	printf("%c %d\n", char(best.n), best.d);
	return 0;
}

UVA – 10986 – Sending email

import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Vector;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws IOException {
		Scanner in = new Scanner(System.in);
		final int MAX_VALUE = 2 << 23;
		int V = -1;
		int kase = 1;
		
		int T =  in.nextInt();
		
		while (T-- != 0) {
			
			int N = in.nextInt(), E = in.nextInt(), S = in.nextInt(), F = in.nextInt();
			Dijkstra d = new Dijkstra(N);
			for (int e = 0; e < E; e++) {
				
				int a = in.nextInt();
				int b = in.nextInt();

				int w = in.nextInt();

				d.addEdge(a, b, w);
				d.addEdge(b, a, w);
			}

			Integer[] a = d.getShortestPathFromTo(S, F);
			System.out.printf("Case #%d: " + (a[0] == MAX_VALUE ? "unreachable" : a[0]) + "\n", kase++);
		}
	}
}

class Dijkstra {
	Integer[] distance;
	ArrayList<Integer>[] adj;
	Integer w[][];
	boolean[] visited;
	final int V;
	final int MAX_VALUE = 2 << 23;
	PriorityQueue<Node> que = new PriorityQueue<Node>();

	@SuppressWarnings("unchecked")
	public Dijkstra(int V_) {
		this.V = V_;
		distance = new Integer[V];
		adj = new ArrayList[V];
		w = new Integer[V][V];
		visited = new  boolean[V];
		for (int i = 0; i < V; i++)
			adj[i] = new ArrayList<Integer>();
	}

	public void addEdge(int a, int b, int W) {
		adj[a].add(b);
		w[a][b] = W;
	}

	public void initSource(int s) {
		Arrays.fill(distance, MAX_VALUE);
		distance[s] = 0;
		
			que.add(new Node(s, distance[s]));
		
	}

	/**
	 * returns an array that is segmented as follows a[0] = the shortest path
	 * weight, a[1] = length of the wieght, a[2] -> a[a.length-1] the path
	 */
	public Integer[] getShortestPathFromTo(int a, int b) {
		initSource(a);
		while(!que.isEmpty()) {
			Node min = que.poll();
			relax(min);
		}
		return new Integer[] { distance[b]};
	}

	private void relax(Node n) {
		int a = n.x;
		for (Integer b : adj[a])
			if (!visited[b] && distance[b] > distance[a] + w[a][b]) {
				distance[b] = distance[a] + w[a][b];
				que.add(new Node(b,distance[b]));
			}
	}
}
class Node implements Comparable<Node>{
	int x;
	int d;
	public Node(int X, int D){
		this.x =X;
		this.d = D;
	}
	@Override
	public int compareTo(Node o) {
		return this.d - o.d;
	}
}

UVA – 341 – Non-Stop Travel

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Vector;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int V = -1;
		int kase = 1;
		while ((V = in.nextInt()) != 0) {
			Dijkstra d = new Dijkstra(V);
			for (int a = 0; a < V; a++) {
				int E = in.nextInt();
				for (int i = 0; i < E; i++) {

					int b = in.nextInt() - 1;
					int w = in.nextInt();

					d.addEdge(a, b, w);
				}
			}

			Integer[] a = d.getShortestPathFromTo(in.nextInt() - 1, in.nextInt() - 1);
			String ans = "";
			for (int i = 2; i <= 1 + a[1]; i++)
				ans += " " + a[i];
			System.out.printf("Case %d: Path =%s; %d second delay\n", kase++, ans, a[0]);
		}
	}
}

class Dijkstra {
	Integer[] distance;
	Integer[] parent;
	ArrayList<Integer>[] adj;
	Integer w[][];
	boolean[] visited;
	final int V;
	final int MAX_VALUE = 2 << 23;

	@SuppressWarnings("unchecked")
	public Dijkstra(int V_) {
		this.V = V_;
		distance = new Integer[V];
		parent = new Integer[V];
		adj = new ArrayList[V];
		w = new Integer[V][V];
		visited = new boolean[V];

		for (int i = 0; i < V; i++)
			adj[i] = new ArrayList<Integer>();
	}

	public void addEdge(int a, int b, int W) {
		adj[a].add(b);
		w[a][b] = W;
	}

	public void initSource(int s) {
		Arrays.fill(distance, MAX_VALUE);
		Arrays.fill(parent, -1);
		distance[s] = 0;
	}

	/**
	 * returns an array that is segmented as follows a[0] = the shortest path
	 * weight, a[1] = length of the wieght, a[2] -> a[a.length-1] the path
	 */
	public Integer[] getShortestPathFromTo(int a, int b) {
		initSource(a);
		for (int i = 0; i < V; i++) {
			int min = minimum();
			visited[min] = true;
			relax(min);
		}

		return getPath(a, b);
	}

	private void relax(int a) {
		for (Integer b : adj[a])
			if (distance[b] > distance[a] + w[a][b]) {
				distance[b] =  distance[a] + w[a][b];
				parent[b] = a;
			}
	}

	private int minimum() {
		int min = -1;
		for (int i = 0; i < V; i++)
			if (!visited[i] && (min == -1 || distance[min] > distance[i]))
				min = i;
		return min;
	}

	private Integer[] getPath(int a, int b) {
		Vector<Integer> p = new Vector<Integer>();

		for (int cur = b; cur != a; cur = parent[cur])
			p.add(cur);
		p.add(a);
		int size = p.size();
		p.add(size);
		p.add(distance[b]);

		Collections.reverse(p);
		Integer[] path = new Integer[p.size()];
		p.toArray(path);
		return path;
	}
}