| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 347938 | TruaShamu | Commuter Pass (JOI18_commuter_pass) | Java | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Main {
public static long ans;
public static ArrayList<Integer[]>[] adj;
public static boolean[] visited = new boolean[100001];
public static long[] du = new long[100001];
public static long[] dv = new long[100001];
public static long[] ds = new long[100001];
public static long[][] dp = new long[2][100001];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
int S = Integer.parseInt(st.nextToken());
int T = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
int U = Integer.parseInt(st.nextToken());
int V = Integer.parseInt(st.nextToken());
adj = new ArrayList[N + 1];
for (int i = 0; i < N + 1; i++) {
adj[i] = new ArrayList<>();
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
adj[a].add(new Integer[]{b, c}); //[[NODE, WEIGHT]]
adj[b].add(new Integer[]{a, c});
}
dijkstra1(U, du);
dijkstra1(V, dv);
ans = du[V];
djikstra2(S, T);
djikstra2(T, S);
System.out.println(ans);
}
public static void dijkstra1(int start, long[] arr) {
Arrays.fill(visited, false);
PriorityQueue<pair> pq = new PriorityQueue<>();
pq.add(new pair(0, start));
while (!pq.isEmpty()) {
long c;
int node;
pair cur = pq.poll();
c = cur.dist;
node = cur.node;
if (!visited[node]) {
arr[node] = c;
visited[node] = true;
for (Integer[] i : adj[node]) {
pq.add(new pair(c + i[1], i[0]));
}
}
}
}
//2ND ROUND
public static void djikstra2(int source, int sink) {
Arrays.fill(dp[0], Long.MAX_VALUE / 2);
Arrays.fill(dp[1], Long.MAX_VALUE / 2);
Arrays.fill(visited, false);
PriorityQueue<item> pq = new PriorityQueue<>();
pq.add(new item(0, source, 0));
dp[0][0] = dp[1][0] = Long.MAX_VALUE / 2;
while (!pq.isEmpty()) {
item cur = pq.poll();
if (!visited[cur.node]) {
visited[cur.node] = true;
ds[cur.node] = cur.cost;
dp[0][cur.node] = Long.min(du[cur.node], dp[0][cur.par]);
dp[1][cur.node] = Long.min(dv[cur.node], dp[1][cur.par]);
for (Integer[] oEdge : adj[cur.node]) {
pq.add(new item(cur.cost + oEdge[1], oEdge[0], cur.node));
}
} else if (cur.cost == ds[cur.node]) {
if (Long.min(du[cur.node], dp[0][cur.par]) + Long.min(dv[cur.node], dp[1][cur.par]) <= dp[0][cur.node] + dp[1][cur.node]) {
dp[0][cur.node] = Long.min(du[cur.node], dp[0][cur.par]);
dp[1][cur.node] = Long.min(dv[cur.node], dp[1][cur.par]);
}
}
}
ans = Long.min(ans, dp[0][sink] + dp[1][sink]);
}
}
class pair implements Comparable<pair> {
public long dist;
public int node;
public pair(long dist, int node) {
this.dist = dist;
this.node = node;
}
public String toString() {
return "A: " + this.dist + " B: " + this.node;
}
public int compareTo(pair other) {
if (this.dist != other.dist) {
return Long.compare(this.dist, other.dist);
}
return Long.compare(this.node, other.node);
}
}
class item implements Comparable<item> {
public long cost;
public int node, par;
public item(long cost, int node, int par) {
this.cost = cost;
this.node = node;
this.par = par;
}
public int compareTo(item other) {
return Long.compare(this.cost, other.cost);
}
}