제출 #490109

#제출 시각아이디문제언어결과실행 시간메모리
490109rainliofficialRobot (JOI21_ho_t4)Java
34 / 100
3085 ms240280 KiB
import java.io.*; import java.util.*; public class Main { static int n, m; static HashMap<Integer, ArrayList<Edge>>[] arr; static HashMap<Integer, Long>[] recolor; // static long[] dp; // dp[i] = min dist to get to node i // static HashMap<Integer, Long>[] dp2; // dp2[i][c] = min cost to get to i, given we just recolored an edge of color c static HashMap<Integer, Long>[][] dist; static int[] edgeColor, edgeCost; static PriorityQueue<State> pq; 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]; recolor = new HashMap[n]; dist = new HashMap[n][2]; // dp = new long[n]; // dp2 = new HashMap[n]; for (int i=0; i<n; i++){ arr[i] = new HashMap<>(); recolor[i] = new HashMap<>(); // dp2[i] = new HashMap<>(); dist[i][0] = new HashMap<>(); dist[i][1] = new HashMap<>(); } int[] edgeColor = new int[m]; int[] edgeCost = new int[m]; 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 c = Integer.parseInt(st.nextToken()); int p = Integer.parseInt(st.nextToken()); if (!recolor[s].containsKey(c)){ recolor[s].put(c, 0L); arr[s].put(c, new ArrayList<>()); } if (!recolor[e].containsKey(c)){ recolor[e].put(c, 0L); arr[e].put(c, new ArrayList<>()); } arr[s].get(c).add(new Edge(e, c, p, i)); arr[e].get(c).add(new Edge(s, c, p, i)); recolor[s].put(c, recolor[s].get(c) + p); recolor[e].put(c, recolor[e].get(c) + p); edgeColor[i] = c; edgeCost[i] = p; } pq = new PriorityQueue<>(); add(0, -1, 0, 0); while (!pq.isEmpty()){ State curr = pq.poll(); if (curr.colorLater == 1){ // We recolored the edge we walked through, so only loop through edges of the same color if (dist[curr.node][1].get(edgeColor[curr.prevEdge]) != curr.cost){ continue; } for (Edge e : arr[curr.node].get(edgeColor[curr.prevEdge])){ if (e.id == curr.prevEdge){ continue; } long nc = curr.cost + recolor[curr.node].get(e.c) - e.p; if (!dist[e.to][0].containsKey(-1) || nc < dist[e.to][0].get(-1)){ pq.add(new State(e.to, e.id, 0, 0, nc)); dist[e.to][0].put(-1, nc); } } }else{ // We didn't recolor the previous edge, so loop through all colors for (int color : arr[curr.node].keySet()){ for (Edge e : arr[curr.node].get(color)){ if (e.id == curr.prevEdge){ continue; } // Recolor edge e, but we don't plan to go through another edge of color e.c (explore all possibilities) long case1 = curr.cost + e.p; if (!dist[e.to][0].containsKey(-1) || case1 < dist[e.to][0].get(-1)){ dist[e.to][0].put(-1, case1); pq.add(new State(e.to, e.id, 0, 1, case1)); } // Recolor all other edges long case2 = curr.cost + recolor[curr.node].get(e.c) - e.p; if (curr.prevEdge != -1 && curr.recolor == 1 && edgeColor[curr.prevEdge] == e.c){ case2 -= edgeCost[curr.prevEdge]; } if (!dist[e.to][0].containsKey(-1) || case2 < dist[e.to][0].get(-1)){ dist[e.to][0].put(-1, case2); pq.add(new State(e.to, e.id, 0, 0, case2)); } // Recolor edge e, and we will go through another edge of color e.c. We will recolor edge e when we get // to e.to, by recoloring all other edges of color e.c (since we will go through another edge of e.c). long case3 = curr.cost; if (!dist[e.to][1].containsKey(e.c) || case3 < dist[e.to][1].get(e.c)){ dist[e.to][1].put(e.c, case3); pq.add(new State(e.to, e.id, 1, 0, case3)); } } } } } long ans = Long.MAX_VALUE; for (long d : dist[n-1][0].values()){ ans = Math.min(ans, d); } if (ans == Long.MAX_VALUE) ans = -1; System.out.println(ans); } public static void add(int node, int prevEdge, int colorLater, long cost){ if (!dist[node][colorLater].containsKey(prevEdge) || cost < dist[node][colorLater].get(prevEdge)){ dist[node][colorLater].put(prevEdge, cost); pq.add(new State(node, prevEdge, colorLater, 0, cost)); } } static class Edge{ int to, c, p, id; public Edge(int to, int c, int p, int id){ this.to = to; this.c = c; this.p = p; this.id = id; } } static class State implements Comparable<State>{ int node, prevEdge, colorLater, recolor; long cost; public State(int node, int prevEdge, int colorLater, int recolor, long cost){ this.node = node; this.prevEdge = prevEdge; this.colorLater = colorLater; this.recolor = recolor; this.cost = cost; } public int compareTo(State o){ return Long.compare(this.cost, o.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...