제출 #1036262

#제출 시각아이디문제언어결과실행 시간메모리
1036262Oz121Robot (JOI21_ho_t4)Java
0 / 100
1571 ms104992 KiB
import java.io.*; import java.util.*; public class Main { public static int num; public static int m; public static HashMap<Integer, Long>[] costs; public static void main(String[] args) throws IOException { BufferedReader scan = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer l1 = new StringTokenizer(scan.readLine()); num = Integer.parseInt(l1.nextToken()); m = Integer.parseInt(l1.nextToken()); ArrayList<ArrayList<Edge>> adj = new ArrayList<>(); costs = new HashMap[num]; for (int i = 0;i<num;i++) { adj.add(new ArrayList<>()); costs[i] = new HashMap<>(); } for (int i = 0;i<m;i++) { StringTokenizer st = new StringTokenizer(scan.readLine()); int a = Integer.parseInt(st.nextToken())-1; int b = Integer.parseInt(st.nextToken())-1; int c = Integer.parseInt(st.nextToken()); int d = Integer.parseInt(st.nextToken()); adj.get(a).add(new Edge(b,c,d)); adj.get(b).add(new Edge(a,c,d)); costs[a].put(c, costs[a].getOrDefault(c,0L)+d); costs[b].put(c, costs[b].getOrDefault(c,0L)+d); } long ans = dijkstra(adj); if (ans==Long.MAX_VALUE) System.out.println(-1); else System.out.println(ans); } public static long dijkstra (ArrayList<ArrayList<Edge>> adj) { HashMap<Integer, Long>[][] dis = new HashMap[num][2]; for (int i = 0;i<num;i++) {dis[i][0] = new HashMap<>(); dis[i][1] = new HashMap<>();} dis[0][0].put(-1,0L); dis[0][1].put(-1,0L); PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingLong(i -> i.cost)); pq.add(new Node(0,new Edge(-1,0,0),0,false)); while (!pq.isEmpty()) { //System.out.println(pq); Node curr = pq.poll(); int node = curr.n; long d = curr.cost; Edge prev = curr.prev; boolean change = curr.change; if (dis[node][toI(change)].get(prev.n)!=d) continue; for (Edge e : adj.get(node)) { int n = e.n; int c = e.c; long w = e.w; if (n==prev.n) continue; long newD1 = d; long newD0 = d; //1 -> New change true; 0 -> New change false. if (change&&prev.c==c) { if (costs[node].get(c)-prev.w-w>w) newD1 += w; else newD0 += costs[node].get(c)-prev.w-w; } else { if (costs[node].get(c)-w>w) newD1 += w; else newD0 += costs[node].get(c)-w; } if (newD0<dis[n][0].getOrDefault(node, Long.MAX_VALUE)) { dis[n][0].put(node, newD0); pq.add(new Node(n,new Edge(node,c,w),newD0,false)); } if (newD1<dis[n][1].getOrDefault(node, Long.MAX_VALUE)) { dis[n][1].put(node,newD1); pq.add(new Node(n,new Edge(node,c,w),newD1,true)); } } } long ans = Long.MAX_VALUE; for (Edge e : adj.get(num-1)) ans = Math.min(ans, Math.min(dis[num-1][0].getOrDefault(e.n, Long.MAX_VALUE),dis[num-1][1].getOrDefault(e.n, Long.MAX_VALUE))); return ans; } public static class Edge { int n; int c; long w; Edge (int n, int c, long w) { this.n = n; this.c = c; this.w = w; } @Override public String toString() { return n+" "+c+" "+w; } } public static class Node { int n; Edge prev; long cost; boolean change; Node (int n, Edge prev, long cost, boolean change) { this.n = n; this.prev = prev; this.cost = cost; this.change = change; } @Override public String toString() { return n+" ["+prev+"] "+cost+" "+change; } } public static int toI (boolean b) { return b ? 1 : 0; } }

컴파일 시 표준 에러 (stderr) 메시지

Note: Main.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...