結果
| 問題 | No.3616 WK vs AT vs MT vs SP |
| コンテスト | |
| ユーザー |
 37zigen
|
| 提出日時 | 2026-08-10 21:19:37 |
| 言語 | Java (openjdk 25.0.2) |
| 結果 |
AC
|
| 実行時間 | 1,023 ms / 2,000 ms |
| + 474µs | |
| コード長 | 11,472 bytes |
| 記録 | |
| コンパイル時間 | 2,340 ms |
| コンパイル使用メモリ | 110,260 KB |
| 実行使用メモリ | 167,208 KB |
| 最終ジャッジ日時 | 2026-08-10 21:19:58 |
| 合計ジャッジ時間 | 20,382 ms |
|
ジャッジサーバーID （参考情報） |
judge3_0 / judge1_0 |
（要ログイン）
| サブタスク | 配点 | 結果 |
|---|---|---|
| サンプル | 0 % | AC * 1 |
| 小課題1 | 8 % | AC * 9 |
| 小課題2 | 16 % | AC * 5 |
| 小課題3 | 20 % | AC * 10 |
| 小課題4 | 20 % | AC * 15 |
| 小課題5 | 20 % | AC * 15 |
| 小課題6 | 16 % | AC * 36 |
| 合計 | 2.5 * 100% = 250 点 |
ソースコード
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintStream;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.AbstractCollection;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map.Entry;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Random;
import java.util.Set;
import java.util.TreeMap;
import java.util.function.BiFunction;
import java.util.function.DoubleUnaryOperator;
import java.util.function.IntUnaryOperator;
import java.util.function.LongToDoubleFunction;
import java.util.function.Predicate;
import java.util.random.RandomGenerator;
public class Main {
static MyPrintWriter pw = MyPrintWriter.getInstance();
static FastScanner sc = FastScanner.getInstance();
public static void main(String[] args) throws IOException {
Thread.setDefaultUncaughtExceptionHandler((t, e) -> System.exit(1));
new Main().run();
pw.flush();
}
void run() {
int N = sc.nextInt();
int R = sc.nextInt();
long C = sc.nextLong();
long[] X = sc.nextLongs(N);
long[] Y = sc.nextLongs(N);
long[] Z = sc.nextLongs(N);
long[] S = sc.nextLongs(N);
LongValueDigraph g = new LongValueDigraph((N + 1) * 8);
for (int i = 0; i < N; i++) {
for (int s = 0; s < (1 << 3); s++) {
if (Ints.bitAt(s, 2) == 1) {
g.addEdge((8 * i) + s, (8 * N) + s, S[i] + C);
g.addEdge((8 * N) + s, (8 * i) + s, S[i]);
}
g.addEdge((8 * i) + s, (8 * i) + (s | (1 << 0)), X[i]);
g.addEdge((8 * i) + s, (8 * i) + (s | (1 << 1)), Y[i]);
g.addEdge((8 * i) + s, (8 * i) + (s | (1 << 2)), Z[i]);
}
}
for (int i = 0; i < R; i++) {
int U = sc.nextInt() - 1;
int V = sc.nextInt() - 1;
long W = sc.nextLong();
long A = sc.nextLong();
long M = sc.nextLong();
for (int swap = 0; swap < 2; swap++) {
for (int s = 0; s < (1 << 3); s++) {
if (Ints.bitAt(s, 1) == 1) {
g.addEdge((8 * U) + s, (8 * V) + s, MathUtils.min(W, A, M));
} else if (Ints.bitAt(s, 0) == 1) {
g.addEdge((8 * U) + s, (8 * V) + s, MathUtils.min(W, A));
} else {
g.addEdge((8 * U) + s, (8 * V) + s, W);
}
}
{
var tmp = U;
U = V;
V = tmp;
}
}
}
var dist = g.dijkstra(0);
long ans = Long.MAX_VALUE;
for (int s = 0; s < (1 << 3); s++) {
ans = Math.min(ans, dist.dist()[(8 * (N - 1)) + s]);
}
pw.println(ans);
}
}
class Edge implements Comparable<Edge> {
public int src;
public int dst;
public long cost;
public Edge(int src, int dst, long cost) {
this.src = src;
this.dst = dst;
this.cost = cost;
}
@Override
public int compareTo(Edge o) {
if (cost != o.cost) {
return Long.compare(cost, o.cost);
} else {
return Integer.compare(dst, o.dst);
}
}
}
class FastScanner {
private static FastScanner instance = null;
private final InputStream in = System.in;
private final byte[] buffer = new byte[1 << 16];
private int ptr = 0;
private int buflen = 0;
private FastScanner() {
}
public static FastScanner getInstance() {
if (instance == null) {
instance = new FastScanner();
}
return instance;
}
private boolean hasNextByte() {
if (ptr < buflen) {
return true;
}
ptr = 0;
try {
buflen = in.read(buffer);
} catch (IOException e) {
e.printStackTrace();
}
return buflen > 0;
}
private int readByte() {
if (hasNextByte()) {
return buffer[ptr++];
} else {
return -1;
}
}
private boolean isPrintableChar(int c) {
return (33 <= c) && (c <= 126);
}
public boolean hasNext() {
while (hasNextByte() && (!isPrintableChar(buffer[ptr]))) {
ptr++;
}
return hasNextByte();
}
public long nextLong() {
if (!hasNext()) {
throw new NoSuchElementException();
}
long n = 0;
boolean minus = false;
int b = readByte();
if (b == '-') {
minus = true;
b = readByte();
}
while ((b >= '0') && (b <= '9')) {
// n = n * 10 + (b - '0');
n = ((n << 1) + (n << 3)) + (b - '0');
b = readByte();
}
return minus ? -n : n;
}
public int nextInt() {
return ((int) (nextLong()));
}
public long[] nextLongs(int n) {
long[] a = new long[n];
for (int i = 0; i < n; ++i) {
a[i] = nextLong();
}
return a;
}
}
class Ints {
public static int bitAt(int binary, int pos) {
if (pos >= 32) {
return 0;
}
return (binary >>> pos) % 2;
}
}
class LongValueDigraph {
public int N;
public int M;
public ArrayList<Edge>[] adj;
@SuppressWarnings("unchecked")
public LongValueDigraph(int N) {
this.N = N;
adj = new ArrayList[N];
for (int i = 0; i < N; ++i) {
adj[i] = new ArrayList<>();
}
}
public void addEdge(int from, int to, long cost) {
if ((from >= N) || (to >= N)) {
throw new AssertionError();
}
adj[from].add(new Edge(from, to, cost));
++M;
}
public record DijkstraResult(long[] dist, int[] parent) {}
/**
* 到達できない頂点 v への距離はLong.MAX_VALUE
* また最短路木の v の親は -1。負辺あるとエラー。
*
* @param src
* @return */
public DijkstraResult dijkstra(int src) {
MyPriorityQueue<long[]> pq = new MyPriorityQueue<>();
pq.add(new long[]{ 0, src });
long[] dist = new long[N];
int[] parent = new int[N];
long INF = Long.MAX_VALUE;
Arrays.fill(dist, INF);
dist[src] = 0;
Arrays.fill(parent, -1);
while (!pq.isEmpty()) {
long[] state = pq.poll();
int v = ((int) (state[1]));
if (dist[v] < state[0]) {
continue;
}
for (var e : adj[v]) {
if (e.cost < 0) {
throw new AssertionError("負の辺が存在");
}
long nd = dist[v] + e.cost;
if (nd < dist[e.dst]) {
dist[e.dst] = nd;
parent[e.dst] = v;
pq.add(new long[]{ nd, e.dst });
}
}
}
return new DijkstraResult(dist, parent);
}
}
class MathUtils {
public static long min(long a, long b) {
return Math.min(a, b);
}
public static long min(long a, long b, long c) {
return MathUtils.min(MathUtils.min(a, b), c);
}
}
class MyPrintWriter extends PrintWriter {
private static MyPrintWriter instance = null;
private MyPrintWriter() {
super(System.out);
}
public static MyPrintWriter getInstance() {
if (instance == null) {
instance = new MyPrintWriter();
}
return instance;
}
}
class MyPriorityQueue<T> extends PriorityQueue<T> {
/**
* デフォルトコンストラクタ: 配列型は Arrays.compare、その他は Comparable
*/
@SuppressWarnings("unchecked")
public MyPriorityQueue() {
super((x, y) -> defaultCompare(x, y));
}
/**
* デフォルト比較: 配列型なら Arrays.compare、その他は Comparable
*/
@SuppressWarnings("unchecked")
private static <T> int defaultCompare(T x, T y) {
if ((x instanceof int[] xi) && (y instanceof int[] yi)) {
return Arrays.compare(xi, yi);
}
if ((x instanceof long[] xl) && (y instanceof long[] yl)) {
return Arrays.compare(xl, yl);
}
if ((x instanceof double[] xd) && (y instanceof double[] yd)) {
return Arrays.compare(xd, yd);
}
if ((x instanceof char[] xc) && (y instanceof char[] yc)) {
return Arrays.compare(xc, yc);
}
if ((x instanceof Comparable cx) && (y instanceof Comparable cy)) {
return cx.compareTo(cy);
}
throw new IllegalArgumentException((("Elements not comparable: " + x.getClass()) + ", ") + y.getClass());
}
}
// --- Original Code ---
//
//
// import java.io.IOException;
// import java.util.Arrays;
//
// import library.tools.FastScanner;
// import library.tools.MergeFiles;
// import library.tools.MyPrintWriter;
// import library.util.Ints;
// import library.util.MathUtils;
// import library.util.graph.LongValueDigraph;
// import library.util.graph.LongValueGraph;
// import library.util.poset.BooleanLattice;
//
// public class Main {
// static MyPrintWriter pw = MyPrintWriter.getInstance();
// static FastScanner sc = FastScanner.getInstance();
//
// public static void main(String[] args) throws IOException {
// new Main().run();
// pw.flush();
// MergeFiles.export();
// }
//
//
// void run() {
// int N=sc.nextInt();
// int R=sc.nextInt();
// long C=sc.nextLong();
// long[]X=sc.nextLongs(N);
// long[]Y=sc.nextLongs(N);
// long[]Z=sc.nextLongs(N);
// long[]S=sc.nextLongs(N);
// LongValueDigraph g=new LongValueDigraph((N+1)*8);
//
// for (int i = 0; i < N; i++) {
// for (int s = 0; s < 1<<3; s++) {
// if (Ints.bitAt(s, 2)==1) {
// g.addEdge(8*i+s, 8*N+s, S[i]+C);
// g.addEdge(8*N+s, 8*i+s, S[i]);
// }
//
// g.addEdge(8*i+s, 8*i+(s|(1<<0)), X[i]);
// g.addEdge(8*i+s, 8*i+(s|(1<<1)), Y[i]);
// g.addEdge(8*i+s, 8*i+(s|(1<<2)), Z[i]);
//
// }
// }
//
// for (int i = 0; i < R; i++) {
// int U=sc.nextInt()-1;
// int V=sc.nextInt()-1;
// long W=sc.nextLong();
// long A=sc.nextLong();
// long M=sc.nextLong();
// for (int swap = 0; swap < 2; swap++) {
//
// for (int s = 0; s < 1<<3; s++) {
// if(Ints.bitAt(s, 1)==1) {
// g.addEdge(8*U+s, 8*V+s, MathUtils.min(W, A, M));
// } else if (Ints.bitAt(s, 0) == 1) {
// g.addEdge(8*U+s, 8*V+s, MathUtils.min(W, A));
// } else {
// g.addEdge(8*U+s, 8*V+s, W);
// }
// }
// {
// var tmp = U;
// U = V;
// V = tmp;
// }
// }
// }
// var dist=g.dijkstra(0);
// long ans=Long.MAX_VALUE;
// for (int s = 0; s < 1<<3; s++) {
// ans=Math.min(ans, dist.dist()[8*(N-1)+s]);
// }
// pw.println(ans);
// }
//
// void tr(Object... objects) {
// System.out.println(Arrays.deepToString(objects));
// }
// }
//