Dijkstra - nise-nabe/topcoder GitHub Wiki

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

        DijkstraMatrix(int n) {
            a = new int[n + 1][n + 1];
            b = new boolean[n + 1];
            q = new PriorityQueue<>(n + 1, Comparator.comparingInt(o -> o[1]));
        }

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

        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;
        }
    }

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);
	}
}