이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
import java.io.*;
import java.util.*;
public class commuter_pass {
public static int num; public static int m; public static long ans;
public static int s; public static int t; public static int u; public static int v;
public static long[] udis; public static long[] vdis;
public static ArrayList<ArrayList<Pair>> adj;
public static void main(String[] args) throws IOException {
BufferedReader scan = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer l1 = new StringTokenizer(scan.readLine());
num = Integer.parseInt(l1.nextToken()); m = Integer.parseInt(l1.nextToken());
StringTokenizer l2 = new StringTokenizer(scan.readLine());
s = Integer.parseInt(l2.nextToken())-1; t = Integer.parseInt(l2.nextToken())-1;
StringTokenizer l3 = new StringTokenizer(scan.readLine());
u = Integer.parseInt(l3.nextToken())-1; v = Integer.parseInt(l3.nextToken())-1;
adj = new ArrayList<>();
for (int i = 0;i<num;i++)
adj.add(new ArrayList<>());
for (int i = 0;i<m;i++) {
StringTokenizer st = new StringTokenizer(scan.readLine());
int a = Integer.parseInt(st.nextToken())-1; int b = Integer.parseInt(st.nextToken())-1; int c = Integer.parseInt(st.nextToken());
adj.get(a).add(new Pair(b,c)); adj.get(b).add(new Pair(a,c));
}
udis = dijkstra1(u); vdis = dijkstra1(v);
ans = udis[v]; dijkstra2();
System.out.println(ans);
}
public static void dijkstra2 () {
long[] dis = new long[num]; Arrays.fill(dis, Long.MAX_VALUE);
PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingLong(a->a.val));
ArrayList<Integer> temp = new ArrayList<>(); temp.add(s);
pq.add(new Node(s,0, temp)); dis[s] = 0;
while (!pq.isEmpty()) {
Node curr = pq.poll(); int node = curr.n; long d = curr.val; ArrayList<Integer> visited = curr.visited;
if (dis[node]!=d) continue;
if (node==t) {
//System.out.println(visited);
long m1 = Long.MAX_VALUE; long m2 = Long.MAX_VALUE;
for (int n : visited) {
m1 = Math.min(m1,udis[n]); m2 = Math.min(m2,vdis[n]);
}
//System.out.println(m1+" "+m2);
ans = Math.min(ans,m1+m2);
continue;
}
for (Pair v : adj.get(node)) {
int n = v.n; long w = v.val;
if (d+w<=dis[n]) {
dis[n] = d+w;
ArrayList<Integer> next = (ArrayList<Integer>) visited.clone(); next.add(n);
pq.add(new Node(n,dis[n], next));
}
}
}
}
public static long[] dijkstra1 (int start) {
long[] dis = new long[num]; Arrays.fill(dis, Long.MAX_VALUE);
PriorityQueue<Pair> pq = new PriorityQueue<>(Comparator.comparingLong(a->a.val));
pq.add(new Pair(start,0)); dis[start] = 0;
while (!pq.isEmpty()) {
Pair curr = pq.poll(); int node = curr.n; long d = curr.val;
if (dis[node]!=d) continue;
for (Pair v : adj.get(node)) {
int n = v.n; long w = v.val;
if (d+w<dis[n]) {
dis[n] = d+w;
pq.add(new Pair(n,dis[n]));
}
}
}
return dis;
}
public static class Pair {
int n; long val; //node to and value (weight or curr dis)
Pair (int n, long val) {
this.n = n; this.val = val;
}
}
public static class Node {
int n; long val; //node to and value (weight or curr dis)
ArrayList<Integer> visited;
Node (int n, long val, ArrayList<Integer> visited) {
this.n = n; this.val = val;
this.visited = visited;
}
}
}
컴파일 시 표준 에러 (stderr) 메시지
Note: commuter_pass.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... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |