제출 #489959

#제출 시각아이디문제언어결과실행 시간메모리
489959rainliofficialRobot (JOI21_ho_t4)Java
34 / 100
3084 ms196840 KiB
import java.io.*; import java.util.*; public class Main { static int n, m; static ArrayList<Edge>[] arr; static HashMap<Integer, Long>[] recolor; 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 ArrayList[n]; recolor = new HashMap[n]; dist = new HashMap[n][2]; for (int i=0; i<n; i++){ arr[i] = new ArrayList<>(); recolor[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()); arr[s].add(new Edge(e, c, p, i)); arr[e].add(new Edge(s, c, p, i)); if (!recolor[s].containsKey(c)){ recolor[s].put(c, 0L); } if (!recolor[e].containsKey(c)){ recolor[e].put(c, 0L); } 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 (dist[curr.node][curr.recolor].get(curr.prevEdge) < curr.cost){ continue; } if (curr.node == n-1){ System.out.println(curr.cost); System.exit(0); } for (Edge e : arr[curr.node]){ if (e.id == curr.prevEdge){ continue; } long nc = recolor[curr.node].get(e.c) - e.p; if (curr.prevEdge != -1 && curr.recolor == 1 && e.c == edgeColor[curr.prevEdge]){ nc -= edgeCost[curr.prevEdge]; } add(e.to, e.id, 0, curr.cost + nc); add(e.to, e.id, 1, curr.cost + e.p); } } System.out.println(-1); } public static void add(int node, int prevEdge, int recolor, long cost){ if (!dist[node][recolor].containsKey(prevEdge) || cost < dist[node][recolor].get(prevEdge)){ dist[node][recolor].put(prevEdge, cost); pq.add(new State(node, prevEdge, recolor, 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, recolor; long cost; public State(int node, int prevEdge, int recolor, long cost){ this.node = node; this.prevEdge = prevEdge; 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...