이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
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, Long>[] 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 HashMap<>();
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, i));
// arr[e].add(new Edge(s, color, cost, i));
addEdge(s, e, color, cost, i);
addEdge(e, s, color, cost, i);
}
// 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<>();
addState(pq, 0, -1, 0, 0, -1);
while (!pq.isEmpty()){
State curr = pq.poll();
if (dist[curr.node].containsKey(curr.prevColor) && dist[curr.node].get(curr.prevColor) != curr.cost){
continue;
}
if (curr.node == n-1){
System.out.println(curr.cost);
System.exit(0);
}
// if (curr.prevColor == -1){
for (int cc : arr[curr.node].keySet()){
for (Edge e : arr[curr.node].get(cc)){
if (!recolor[curr.node].containsKey(e.color) || e.id == curr.prevEdgeId){
continue;
}
long nc = curr.cost + recolor[curr.node].get(e.color) - e.cost;
if (curr.prevColor == e.color){
nc -= curr.prevEdgeCost;
}
addState(pq, e.to, -1, nc, e.cost, e.id);
addState(pq, e.to, e.color, curr.cost + e.cost, e.cost, e.id);
}
}
// }else{
// for (Edge e : arr[curr.node].get(curr.prevColor)){
// if (!recolor[curr.node].containsKey(e.color) || e.id == curr.prevEdgeId){
// continue;
// }
// long nc = curr.cost + recolor[curr.node].get(e.color) - e.cost;
// if (curr.prevColor == e.color){
// nc -= curr.prevEdgeCost;
// }
// addState(pq, e.to, -1, nc, e.cost, e.id);
// addState(pq, e.to, e.color, curr.cost + e.cost, e.cost, e.id);
// }
// }
}
System.out.println(-1);
}
public static void addEdge(int ind, int to, int color, int cost, int id){
if (!recolor[ind].containsKey(color)){
arr[ind].put(color, new ArrayList<>());
recolor[ind].put(color, 0L);
}
arr[ind].get(color).add(new Edge(to, color, cost, id));
recolor[ind].put(color, recolor[ind].get(color) + (long)cost);
}
public static void addState(PriorityQueue<State> pq, int ind, int prevColor, long newDist, int prevEdgeCost, int id){
if (!dist[ind].containsKey(prevColor) || dist[ind].get(prevColor) > newDist){
dist[ind].put(prevColor, newDist);
pq.add(new State(ind, prevColor, newDist, prevEdgeCost, id));
}
}
static class State implements Comparable<State>{
int node, prevColor, prevEdgeCost, prevEdgeId;
long cost;
public State(int node, int prevColor, long cost, int prevEdgeCost, int prevEdgeId){
this.node = node;
this.prevColor = prevColor;
this.cost = cost;
this.prevEdgeCost = prevEdgeCost;
this.prevEdgeId = prevEdgeId;
}
public int compareTo(State o){
return Long.compare(this.cost, o.cost);
}
}
static class Edge{
int to, color, cost, id;
public Edge(int to, int color, int cost, int id){
this.to = to;
this.color = color;
this.cost = cost;
this.id = id;
}
}
}
컴파일 시 표준 에러 (stderr) 메시지
Note: Main.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |