LightOJ 1019 - Brush (V) http://lightoj.com/volume_showproblem.php?problem=1019 最短路

LightOJ1019.java

import java.io.BufferedReader;
import java.io.IOError;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.StringTokenizer;

public class P1019 {

        class Edge {
		int v;
		int w;
		Edge next;

		Edge(int v, int w, Edge next) {
			this.v = v;
			this.w = w;
			this.next = next;
		}
	}

	public void run() {
		Scanner cin = new Scanner(System.in);
		PrintWriter cout = new PrintWriter(new OutputStreamWriter(System.out));

		int test = cin.nextInt();
		for (int cas = 1; cas <= test; cas++) {
			cout.print("Case " + cas + ": ");
			int n = cin.nextInt();
			int m = cin.nextInt();
			Edge[] graph = new Edge[n + 1];
			int[] dis = new int[n + 1];
			for (int i = 0; i < m; i++) {
				int u = cin.nextInt();
				int v = cin.nextInt();
				int w = cin.nextInt();
				graph[u] = new Edge(v, w, graph[u]);
				graph[v] = new Edge(u, w, graph[v]);
			}
			ArrayDeque<Integer> que = new ArrayDeque<Integer>(n);
			boolean[] inque = new boolean[n + 1];
			Arrays.fill(dis, Integer.MAX_VALUE);
			dis[1] = 0;
			que.add(1);
			inque[1] = true;
			while (!que.isEmpty()) {
				int u = que.poll();
				inque[u] = false;
				for (Edge it = graph[u]; it != null; it = it.next) {
					if (dis[it.v] > dis[u] + it.w) {
						dis[it.v] = dis[u] + it.w;
						if (!inque[it.v]) {
							que.add(it.v);
							inque[it.v] = true;
						}
					}
				}
			}
			if (dis[n] < Integer.MAX_VALUE) {
				cout.println(dis[n]);
			} else {
				cout.println("Impossible");
			}
		}

		cout.flush();
	}

	public static void main(String args[]) {
		new P1019().run();
	}

	class Scanner {

		BufferedReader br;
		StringTokenizer st;

		Scanner(InputStream in) {
			br = new BufferedReader(new InputStreamReader(in));
			eat("");
		}

		void eat(String s) {
			st = new StringTokenizer(s);
		}

		String nextLine() {
			try {
				return br.readLine();
			} catch (IOException e) {
				throw new IOError(e);
			}
		}

		boolean hasNext() {
			while (!st.hasMoreTokens()) {
				String s = nextLine();
				if (s == null)
					return false;
				eat(s);
			}
			return true;
		}

		String next() {
			hasNext();
			return st.nextToken();
		}

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

		long nextLong() {
			return Long.parseLong(next());
		}

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

}