이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException, FileNotFoundException {
// Scanner in = new Scanner(new File("test.in"));
Kattio in = new Kattio();
int N = in.nextInt();
int M = in.nextInt();
ArrayList<Road>[] adj = new ArrayList[N];
for(int i = 0; i < N; i++){
adj[i] = new ArrayList<>();
}
for(int i = 0; i < M; i++){
int a = in.nextInt() - 1;
int b = in.nextInt() - 1;
int color = in.nextInt();
int cost = in.nextInt();
adj[a].add(new Road(a, b, color, cost));
adj[b].add(new Road(b, a, color, cost));
}
PriorityQueue<State> pq = new PriorityQueue<>();
pq.add(new State(0, 0));
boolean[] visited = new boolean[N];
long ans = -1;
while(!pq.isEmpty()){
State curr = pq.poll();
if(visited[curr.pos]){
continue;
}
visited[curr.pos] = true;
if(curr.pos == N - 1){
ans = curr.dist;
}
// go to each one and see the count
HashMap<Integer, Integer> co = new HashMap<>();
for(Road r: adj[curr.pos]){
if(!co.containsKey(r.color)){
co.put(r.color, r.cost);
} else {
co.put(r.color, co.get(r.color) + r.cost);
}
}
for(Road r: adj[curr.pos]){
pq.add(new State(r.to, Math.min(curr.dist + r.cost, curr.dist + co.get(r.color) - r.cost)));
}
}
System.out.println(ans);
}
static class Kattio extends PrintWriter {
private BufferedReader r;
private StringTokenizer st;
// standard input
public Kattio() { this(System.in, System.out); }
public Kattio(InputStream i, OutputStream o) {
super(o);
r = new BufferedReader(new InputStreamReader(i));
}
// USACO-style file input
public Kattio(String problemName) throws IOException {
super(new FileWriter(problemName + ".out"));
r = new BufferedReader(new FileReader(problemName + ".in"));
}
// returns null if no more input
public String next() {
try {
while (st == null || !st.hasMoreTokens())
st = new StringTokenizer(r.readLine());
return st.nextToken();
} catch (Exception e) { }
return null;
}
public int nextInt() { return Integer.parseInt(next()); }
public double nextDouble() { return Double.parseDouble(next()); }
public long nextLong() { return Long.parseLong(next()); }
}
public static class State implements Comparable<State>{
int pos;
long dist;
public State(int pos, long dist){
this.pos = pos;
this.dist = dist;
}
public int compareTo(State s){
return Long.compare(dist, s.dist);
}
}
public static class Road {
int a, to, color, cost;
public Road(int a, int to, int color, int cost){
this.a = a;
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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |