質問する

N都市があります.ある都市から別の都市へ行くM台のバスもあります.私たちはAからBまでのバスの料金を最小限に抑えたいです.AからBまでの最小費用をプリントアウトします.都市番号は1からNです.

入力

1行目は都市の個数N(1≦N≦1000)を与え、2行目はバスの個数M(1≦M≦100000)を与える.次に、3行目からM+2行目まで、次のバスの情報が提供されます.まず、最初にそのバスの出発都市番号をあげます.そして到着地のシティナンバー、そしてバス代です.バス料金は0以上、100000未満の整数です.
そしてM+3行は私たちが要求した区間起点の都市番号と到着点の都市番号を与えた.始点で終点に到達できる場合のみ入力します.

しゅつりょく

最初の行は、出発都市から到着都市までの最小費用を出力します.

に答える

問題で要求される最小コストを最短距離と見なし,Dijkstraアルゴリズムを用いて解決できる.
最低コストを格納するシナリオを作成し、優先キュー(PriorityQueue)を使用して、低コストで更新を続行します.
出力は,最小コストを格納する配列から到達点に対応する内容を出力するだけでよい.

ソース

import java.util.*;

class Node implements Comparable<Node> {
	private int index;
	private int distance;

	public Node(int index, int distance) {
		this.index = index;
		this.distance = distance;
	}

	public int getIndex() {
		return this.index;
	}

	public int getDistance() {
		return this.distance;
	}

	@Override
	public int compareTo(Node o) {
		if (this.distance < o.distance) {
			return -1;
		}
		return 1;
	}
}

public class Main {
	public static final int INF = (int) 1e9;
	// 도시의 개수(n), 버스의 개수(m), 시작점(start), 도착점(end)
	public static int n, m, start, end;

	public static ArrayList<ArrayList<Node>> graph = new ArrayList<ArrayList<Node>>();
	public static int[] d = new int[1001];

	public static void dijkstra(int start) {
		PriorityQueue<Node> pq = new PriorityQueue<Node>();

		pq.offer(new Node(start, 0));
		d[start] = 0;

		while (!pq.isEmpty()) {
			Node node = pq.poll();
			int dist = node.getDistance();
			int now = node.getIndex();

			if (d[now] < dist)
				continue;

			for (int i = 0; i < graph.get(now).size(); i++) {
				int cost = d[now] + graph.get(now).get(i).getDistance();

				if (cost < d[graph.get(now).get(i).getIndex()]) {
					d[graph.get(now).get(i).getIndex()] = cost;
					pq.offer(new Node(graph.get(now).get(i).getIndex(), cost));
				}
			}
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		n = sc.nextInt();
		m = sc.nextInt();

		for (int i = 0; i <= n; i++) {
			graph.add(new ArrayList<Node>());
		}

		for (int i = 0; i < m; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			int cost = sc.nextInt();

			graph.get(a).add(new Node(b, cost));
		}

		Arrays.fill(d, INF);

		start = sc.nextInt();
		end = sc.nextInt();

		dijkstra(start);

		System.out.println(d[end]);
	}

}