結果

問題 No.3712 Urban Train
コンテスト
ユーザー ks2m
提出日時 2026-09-11 22:02:22
言語 Java
(openjdk 26.0.2.1 + ACL)
コンパイル:
javac -J-Duser.language=en -encoding UTF8 -cp /opt/aclib/ac_library.jar _filename_
実行:
java -ea -Xmx700m -Xss256M -DONLINE_JUDGE=true -cp .:/opt/aclib/ac_library.jar _class_
結果
AC  
実行時間 884 ms / 2,000 ms
+ 31µs
コード長 2,168 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,566 ms
コンパイル使用メモリ 90,012 KB
実行使用メモリ 95,980 KB
最終ジャッジ日時 2026-09-11 22:02:40
合計ジャッジ時間 12,548 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 39
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] sa = br.readLine().split(" ");
		int n = Integer.parseInt(sa[0]);
		int m = Integer.parseInt(sa[1]);
		List<List<Hen>> list = new ArrayList<>(n);
		for (int i = 0; i < n; i++) {
			list.add(new ArrayList<>());
		}
		for (int i = 0; i < m; i++) {
			sa = br.readLine().split(" ");
			int a = Integer.parseInt(sa[0]) - 1;
			int b = Integer.parseInt(sa[1]) - 1;
			int c = Integer.parseInt(sa[2]);

			list.get(a).add(new Hen(b, c));
			list.get(b).add(new Hen(a, c));
		}

		sa = br.readLine().split(" ");
		int[] a = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = Integer.parseInt(sa[i]);
		}
		sa = br.readLine().split(" ");
		int[] b = new int[n];
		for (int i = 0; i < n; i++) {
			b[i] = Integer.parseInt(sa[i]);
		}
		sa = br.readLine().split(" ");
		int[] c = new int[n];
		for (int i = 0; i < n; i++) {
			c[i] = Integer.parseInt(sa[i]);
		}
		br.close();

		int s = 0;
		long[] d = new long[list.size()];
		Arrays.fill(d, Long.MAX_VALUE);
		d[s] = a[0];
		PriorityQueue<Node> que = new PriorityQueue<Node>();
		que.add(new Node(s, a[0]));

		while (!que.isEmpty()) {
			Node cur = que.poll();
			int cv = cur.v;
			if (cur.d > d[cv]) {
				continue;
			}
			long cd = cur.d;
			if (cd % a[cv] != 0) {
				cd += a[cv] - cd % a[cv];
			}
			if (cd / a[cv] % b[cv] == 0) {
				cd += Math.min(a[cv], c[cv]);
			}
			for (Hen hen : list.get(cv)) {
				long alt = cd + hen.c;
				if (alt < d[hen.v]) {
					d[hen.v] = alt;
					que.add(new Node(hen.v, alt));
				}
			}
		}
		System.out.println(d[n - 1]);
	}

	static class Hen {
		int v, c;

		public Hen(int v, int c) {
			this.v = v;
			this.c = c;
		}
	}

	static class Node implements Comparable<Node> {
		int v;
		long d;

		public Node(int v, long d) {
			this.v = v;
			this.d = d;
		}

		public int compareTo(Node o) {
			return Long.compare(d, o.d);
		}
	}
}
0