import java.io.IOException; import java.util.ArrayList; import java.util.Arrays; import java.util.PriorityQueue; public class Main { static int v, e; static int v1, v2; static ArrayList[] edges; public static void main(String[] args) throws Exception { v = readInt(); e = readInt(); edges = new ArrayList[v]; for (int i=0; i(); for (int i=0; i queue = new PriorityQueue<>(); int initialBitmask = 0; if (v1 == 0) { initialBitmask = 0b01; } if (v2 == v-1) { initialBitmask |= 0b10; } dis[initialBitmask][0] = 0; queue.add(new State(0, 0, initialBitmask)); while (!queue.isEmpty()) { State cur = queue.poll(); int x = cur.x; int d = cur.d; int bitmask = cur.bitmask; for (Edge e : edges[x]) { int end = e.end; int weight = e.weight; if (end == v-1) { if (bitmask == 0b11) { return dis[0b11][x] + weight; } else { if (d + weight < dis[bitmask][end]) { dis[bitmask][end] = d + weight; queue.add(new State(end, dis[bitmask][end], bitmask)); } } } else if (end == v1) { int newBitmask = bitmask | 0b01; if (d + weight < dis[newBitmask][end]) { dis[newBitmask][end] = d + weight; queue.add(new State(end, dis[newBitmask][end], newBitmask)); } } else if (end == v2) { int newBitmask = bitmask | 0b10; if (d + weight < dis[newBitmask][end]) { dis[newBitmask][end] = d + weight; queue.add(new State(end, dis[newBitmask][end], newBitmask)); } } else { if (d + weight < dis[bitmask][end]) { dis[bitmask][end] = d + weight; queue.add(new State(end, dis[bitmask][end], bitmask)); } } } } return -1; } static int readInt() throws IOException { int x = System.in.read() & 15; int y = System.in.read(); while (y > 47) { x = (x << 3) + (x << 1) + (y & 15); y = System.in.read(); } return x; } static class Edge { int end; int weight; public Edge(int end, int weight) { this.end = end; this.weight = weight; } } static class State implements Comparable { int x; int d; int bitmask; public State(int x, int d, int bitmask) { this.x = x; this.d = d; this.bitmask = bitmask; } @Override public int compareTo(State o) { return Integer.compare(this.d, o.d); } } }

제출 #22875

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: