제출 #489733

#제출 시각아이디문제언어결과실행 시간메모리
489733rainliofficialRobot (JOI21_ho_t4)Java
0 / 100
3082 ms492540 KiB
import java.io.*; import java.util.*; public class Main { static int n, m; static ArrayList<Edge>[] arr; static HashMap<Integer, Long>[] dist; //static HashMap<Integer, ArrayList<Edge>>[] arr; static HashMap<Integer, Integer>[] recolor; // Stores the cost to recolor all edges of a certain color at a node public static void main(String[] args) throws IOException{ BufferedReader file = new BufferedReader(new InputStreamReader(System.in)); //BufferedReader file = new BufferedReader(new FileReader("file.in")); // PrintWriter outfile = new PrintWriter (new BufferedWriter(new FileWriter("Robot.out"))); StringTokenizer st = new StringTokenizer(file.readLine()); n = Integer.parseInt(st.nextToken()); m = Integer.parseInt(st.nextToken()); //arr = new HashMap[n]; arr = new ArrayList[n]; recolor = new HashMap[n]; dist = new HashMap[n]; recolor = new HashMap[n]; for (int i=0; i<n; i++){ arr[i] = new ArrayList<>(); recolor[i] = new HashMap<>(); dist[i] = new HashMap<>(); recolor[i] = new HashMap<>(); } for (int i=0; i<m; i++){ st = new StringTokenizer(file.readLine()); int s = Integer.parseInt(st.nextToken())-1; int e = Integer.parseInt(st.nextToken())-1; int color = Integer.parseInt(st.nextToken()); int cost = Integer.parseInt(st.nextToken()); arr[s].add(new Edge(e, color, cost)); arr[e].add(new Edge(s, color, cost)); addEdge(s, e, color, cost); addEdge(e, s, color, cost); } // Do Dijkstra on expanded states. State = current node, the original color of the edge we just walked through, // (if we recolored it). Total N+M states. PriorityQueue<State> pq = new PriorityQueue<>(); pq.add(new State(0, -1, 0, 0)); while (!pq.isEmpty()){ State curr = pq.poll(); if (dist[curr.node].containsKey(curr.prevColor) && dist[curr.node].get(curr.prevColor) != curr.cost){ continue; } addUsed(curr.node, curr.prevColor, curr.cost); for (Edge e : arr[curr.node]){ // if (curr.prevColor == e.color || curr.prevColor == -1){ if (!recolor[curr.node].containsKey(e.color)){ continue; } // Determine to recolor all other edges of the same color, or recolor this 1 edge // if (recolor[curr.node].get(e.color) - curr.prevEdgeCost - e.cost <= e.cost){ // Recolor everything else long nc = curr.cost + recolor[curr.node].get(e.color) - e.cost; if (curr.prevColor == e.color){ nc -= curr.prevEdgeCost; } if (addUsed(e.to, -1, nc)){ pq.add(new State(e.to, -1, nc, e.cost)); } // }else if (recolor[curr.node].get(e.color) - curr.prevEdgeCost - e.cost >= e.cost){ if (addUsed(e.to, e.color, curr.cost + e.cost)){ pq.add(new State(e.to, e.color, curr.cost + e.cost, e.cost)); } // } // } } // if (curr.prevColor != -1){ // // Loop through the edges with color = prevColor // for (Edge e : arr[curr.node].get(curr.prevColor)){ // if (recolor[curr.node].get(curr.prevColor) - curr.prevEdgeCost >; // if (dist[e.to].containsKey(e.color) && dist[e.to].get(e.color) <= nc + curr.cost){ // } // } // }else{ // for (int color : arr[curr.node].keySet()){ // for (Edge e : arr[curr.node].get(color)){ // } // } // } } long ans = Long.MAX_VALUE; for (int c : dist[n-1].keySet()){ ans = Math.min(dist[n-1].get(c), ans); } if (ans == Long.MAX_VALUE) ans = -1; System.out.println(ans); } public static void addEdge(int ind, int to, int color, int cost){ if (!recolor[ind].containsKey(color)){ // arr[ind].put(color, new ArrayList<>()); recolor[ind].put(color, 0); } // arr[ind].get(color).add(new Edge(to, color, cost)); recolor[ind].put(color, recolor[ind].get(color) + cost); } public static boolean addUsed(int ind, int prevColor, long newDist){ // Return true if element added, or false if not added if (!dist[ind].containsKey(prevColor) || dist[ind].get(prevColor) > newDist){ dist[ind].put(prevColor, newDist); return true; } return false; } static class State implements Comparable<State>{ int node, prevColor, prevEdgeCost; long cost; public State(int node, int prevColor, long cost, int prevEdgeCost){ this.node = node; this.prevColor = prevColor; this.cost = cost; this.prevEdgeCost = prevEdgeCost; } public int compareTo(State o){ return Long.compare(this.cost, o.cost); } } static class Edge{ int to, color, cost; public Edge(int to, int color, int cost){ this.to = to; this.color = color; this.cost = cost; } } }

컴파일 시 표준 에러 (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...