JAVA Dijkstra最短優先キュー最適化テンプレートHDU 2544
最近ブルーブリッジカップに備えて、JAVA組に惑わされて、波の経験を送りましたが、面白いコードも書きました.今日はまず、自分が書いたJAVA版Dijkstraの最短スタック最適化版コードを共有します.
本コードは隣接テーブル(List)方式で図を定義し、HDU 2544上で正しくAC
本コードは隣接テーブル(List)方式で図を定義し、HDU 2544上で正しくAC
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
while (true) {
int n = cin.nextInt(), m = cin.nextInt();
if(n==0&m==0)break;
List> vec = new ArrayList<>();
for (int i = 0; i < n + 5; i++) {
vec.add(new ArrayList<>());
}
int dis[] = new int[n + 5];
boolean vis[] = new boolean[n + 5];
for (int i = 0; i < m; i++) {
int a = cin.nextInt(), b = cin.nextInt(), c = cin.nextInt();
vec.get(a).add(new Edge(b, c));
vec.get(b).add(new Edge(a,c));
}
for (int i = 0; i <= n; i++) {
dis[i] = Integer.MAX_VALUE;
vis[i] = false;
}
dis[1] = 0;
PriorityQueue queue = new PriorityQueue<>();
queue.add(new Node(1, 0));
while (!queue.isEmpty()) {
Node now = queue.poll();
if (vis[now.point]) {
continue;
}
vis[now.point] = true;
for (int i = 0; i < vec.get(now.point).size(); i++) {
Edge nxt = vec.get(now.point).get(i);
if (nxt.val + dis[now.point] < dis[nxt.to]) {
dis[nxt.to] = nxt.val + dis[now.point];
queue.add(new Node(nxt.to, dis[nxt.to]));
}
}
}
System.out.println(dis[n]);
}
}
}
class Edge{
int to,val;
public Edge(int to,int val){
this.to=to;
this.val=val;
}
}
class Node implements Comparable{
int point,val;
public Node(int point,int val){
this.val=val;
this.point=point;
}
@Override
public int compareTo(Node node){
return val-node.val;
}
}