250713 탐사

private static final int INF = 54321;

private static class Edge {
	int to, weight;

	Edge(int to, int weight) {
		this.to = to;
		this.weight = weight;
	}
}

public static void main(String[] args) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer st = new StringTokenizer(br.readLine());

	int n = Integer.parseInt(st.nextToken());
	int m = Integer.parseInt(st.nextToken());
	int src = n + 1;

	List<List<Edge>> adj = new ArrayList<>();
	for (int i = 0; i <= n + 1; i++) {
		adj.add(new ArrayList<>());
	}

	while (m-- > 0) {
		st = new StringTokenizer(br.readLine());
		int x = Integer.parseInt(st.nextToken()) - 1;
		int y = Integer.parseInt(st.nextToken());
		int r = Integer.parseInt(st.nextToken());

		adj.get(x).add(new Edge(y, r));
		adj.get(y).add(new Edge(x, -r));
	}

	for (int i = 0; i <= n; i++) {
		if (i > 0) {
			adj.get(i - 1).add(new Edge(i, 1));
			adj.get(i).add(new Edge(i - 1, 0));
		}
		adj.get(src).add(new Edge(i, 0));
	}

	int[] dist = new int[n + 2];
	boolean[] inQueue = new boolean[n + 2];
	for (int i = 0; i <= n + 1; i++)
		dist[i] = INF;

	if (!spfa(src, adj, dist, inQueue, n)) {
		System.out.print("NONE");
		return;
	}

	StringBuilder sb = new StringBuilder();
	for (int i = 1; i <= n; i++) {
		sb.append(dist[i] == dist[i - 1] ? '-' : '#');
	}
	System.out.print(sb);
}

private static boolean spfa(int src, List<List<Edge>> adj, int[] dist, boolean[] inQueue, int n) {
	Queue<Integer> queue = new ArrayDeque<>();
	dist[src] = 0;
	inQueue[src] = true;
	queue.offer(src);

	int iteration = 0;
	while (!queue.isEmpty()) {
		if (++iteration > n + 5)
			return false;
		int size = queue.size();

		for (int i = 0; i < size; i++) {
			int u = queue.poll();
			inQueue[u] = false;

			for (Edge edge : adj.get(u)) {
				int v = edge.to;
				int newCost = dist[u] + edge.weight;

				if (newCost < dist[v]) {
					dist[v] = newCost;
					if (!inQueue[v]) {
						inQueue[v] = true;
						queue.offer(v);
					}
				}
			}
		}
	}
	return true;
}

출처:https://www.acmicpc.net/problem/7577