ダイクストラ法をJavaで書く．

たぶんダイクストラ法と呼ばれるものだと思う．

何回も書くのがめんどそうなのでクラス化．

隣接行列実装

static class DijkstraMatrix {
	int[][] a;
	boolean[] b;
	PriorityQueue<int[]> q;

	public DijkstraMatrix(int n) {
		a = new int[n + 1][n + 1];
		b = new boolean[n + 1];
		q = new PriorityQueue<int[]>(n + 1, new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				return o1[1] - o2[1];
			}
		});
	}

	public void set(int i, int j, int cost) {
		a[i][j] = cost;
	}

	public int getCost(int s, int e) {
		Arrays.fill(b, false);
		q.clear();
		b[s] = true;
		for (int i = 1; i < a.length; ++i)
			if (a[s][i] > 0)
				q.add(new int[] { i, a[s][i] });
		int c = 0;
		while (!q.isEmpty()) {
			int[] t = q.poll();
			if (t[0] == e) {
				c = t[1];
				break;
			}
			b[t[0]] = true;
			for (int i = 1; i < a.length; ++i)
				if (!b[i] && a[t[0]][i] > 0)
					q.add(new int[] { i, t[1] + a[t[0]][i] });
		}
		return c;
	}

}

使い方（SPOJ3700 EZDIJKST)

public static void main(String[] args) throws Exception{
	for(int t=next();t-->0;){
		DijkstraMatrix dijkst=new DijkstraMatrix(next());
		for(int k=next();k-->0;){
			int i=next();
			int j=next();
			int cost=next();
			dijkst.set(i, j, cost);
		}
		int start = next();
		int end = next();
		int cost = dijkst.getCost(start, end);
		System.out.println(cost<1?"NO":cost);
	}
}