結果

問題 No.160 最短経路のうち辞書順最小
ユーザー kenkooookenkoooo
提出日時 2015-03-07 03:05:20
言語 Java21
(openjdk 21)
結果
AC  
実行時間 136 ms / 5,000 ms
コード長 3,289 bytes
コンパイル時間 2,552 ms
コンパイル使用メモリ 79,688 KB
実行使用メモリ 53,200 KB
最終ジャッジ日時 2024-06-24 15:05:16
合計ジャッジ時間 6,485 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 57 ms
49,820 KB
testcase_01 AC 56 ms
50,204 KB
testcase_02 AC 55 ms
50,132 KB
testcase_03 AC 55 ms
49,964 KB
testcase_04 AC 100 ms
51,748 KB
testcase_05 AC 107 ms
52,288 KB
testcase_06 AC 116 ms
52,724 KB
testcase_07 AC 92 ms
51,152 KB
testcase_08 AC 96 ms
50,936 KB
testcase_09 AC 97 ms
51,584 KB
testcase_10 AC 96 ms
53,200 KB
testcase_11 AC 93 ms
51,256 KB
testcase_12 AC 84 ms
51,144 KB
testcase_13 AC 93 ms
51,152 KB
testcase_14 AC 93 ms
51,048 KB
testcase_15 AC 95 ms
51,124 KB
testcase_16 AC 94 ms
50,988 KB
testcase_17 AC 97 ms
51,212 KB
testcase_18 AC 94 ms
50,804 KB
testcase_19 AC 98 ms
51,288 KB
testcase_20 AC 94 ms
51,256 KB
testcase_21 AC 91 ms
51,276 KB
testcase_22 AC 93 ms
51,116 KB
testcase_23 AC 91 ms
51,304 KB
testcase_24 AC 95 ms
51,736 KB
testcase_25 AC 97 ms
51,228 KB
testcase_26 AC 92 ms
51,084 KB
testcase_27 AC 59 ms
50,288 KB
testcase_28 AC 136 ms
52,748 KB
testcase_29 AC 58 ms
50,180 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;

public class Main {

	public static void main(String[] args) {
		int N = nextInt();
		int M = nextInt();
		int start = nextInt();
		int goal = nextInt();

		Graph graph = new Graph(N);
		for (int i = 0; i < M; i++) {
			int a = nextInt();
			int b = nextInt();
			int c = nextInt();
			graph.addBidirectionalEdge(a, b, c);
		}

		int[] dist = graph.minDistDijkstra(goal);

		ArrayList<Integer> list = new ArrayList<>();
		int now = start;
		list.add(now);
		while (true) {
			if (now == goal) {
				break;
			}
			int next = Integer.MAX_VALUE;
			for (Graph.Edge edge : graph.graph[now]) {
				// nowから出ている全ての辺を見る
				if (dist[now] == dist[edge.to] + edge.cost) {
					// goalからedge.toを通ってnowへ行く経路が最短経路だったとき
					next = Math.min(edge.to, next);
				}
			}
			list.add(next);
			now = next;
		}
		StringBuilder sb = new StringBuilder();
		for (Integer integer : list) {
			sb.append(integer);
			if (integer != goal) {
				sb.append(" ");
			}
		}
		System.out.println(sb.toString());
	}

	static int nextInt() {
		int c;
		try {
			c = System.in.read();
			while (c != '-' && (c < '0' || c > '9'))
				c = System.in.read();
			if (c == '-')
				return -nextInt();
			int res = 0;
			while (c >= '0' && c <= '9') {
				res = res * 10 + c - '0';
				c = System.in.read();
			}
			return res;
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		return -1;
	}

}

class Graph {
	public static final int INF = 1 << 29;
	int n;
	ArrayList<Edge>[] graph;

	@SuppressWarnings("unchecked")
	public Graph(int n) {
		this.n = n;
		this.graph = new ArrayList[n];
		for (int i = 0; i < n; i++) {
			graph[i] = new ArrayList<Edge>();
		}
	}

	public void addBidirectionalEdge(int from, int to, int cost) {
		addEdge(from, to, cost);
		addEdge(to, from, cost);
	}

	public void addEdge(int from, int to, int cost) {
		graph[from].add(new Edge(to, cost));
	}

	// dijkstra O(ElogV)
	public int[] minDistDijkstra(int start) {
		int[] dist = new int[n];
		Arrays.fill(dist, INF);
		dist[start] = 0;

		PriorityQueue<Node> priorityQueue = new PriorityQueue<Node>();
		priorityQueue.offer(new Node(0, start));

		while (!priorityQueue.isEmpty()) {
			// キューから1番距離の近いノードを取り出す
			Node node = priorityQueue.poll();
			int v = node.id;
			if (dist[v] < node.dist) {
				// 暫定の最短距離よりも遠かったらスルー
				continue;
			}

			for (Edge e : graph[v]) {
				/*
				 * 取り出したノードから出ている全ての辺について調べ、 暫定の最短距離が更新される場合は更新してキューに入れる
				 */
				if (dist[e.to] > dist[v] + e.cost) {
					dist[e.to] = dist[v] + e.cost;
					priorityQueue.add(new Node(dist[e.to], e.to));
				}
			}
		}
		return dist;
	}

	class Edge {
		int to;
		int cost;

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

	class Node implements Comparable<Node> {
		int dist;
		int id;

		public Node(int dist, int i) {
			this.dist = dist;
			this.id = i;
		}

		public int compareTo(Node o) {
			return this.dist - o.dist;
		}
	}
}
0