結果
| 問題 |
No.788 トラックの移動
|
| コンテスト | |
| ユーザー |
 kusomushi
|
| 提出日時 | 2019-07-31 21:43:33 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 1,078 ms / 2,000 ms |
| コード長 | 7,069 bytes |
| コンパイル時間 | 2,878 ms |
| コンパイル使用メモリ | 84,744 KB |
| 実行使用メモリ | 86,780 KB |
| 最終ジャッジ日時 | 2024-12-15 07:05:43 |
| 合計ジャッジ時間 | 10,732 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 14 |
ソースコード
import java.io.*;
import java.util.*;
public class Main {
static int N, M, L;
static int[] T;
static Edge[] E;
public static void main(String[] args) {
FastScanner sc = new FastScanner(System.in);
N = sc.nextInt();
M = sc.nextInt();
L = sc.nextInt()-1;
T = sc.nextIntArray(N);
E = new Edge[M];
for (int i = 0; i < M; i++) {
E[i] = new Edge(sc.nextInt()-1, sc.nextInt()-1, sc.nextInt());
}
System.out.println(solve());
}
static class Edge {
int a, b, c;
public Edge(int a, int b, int c) {
this.a = a;
this.b = b;
this.c = c;
}
}
static long solve() {
if( isAlreadyDone() ) return 0;
Edge[][] G = adjB(N, E);
long[][] dist = new long[N][];
for (int i = 0; i < N; i++) {
dist[i] = calcDist(i, G);
}
long ans = Long.MAX_VALUE/2;
for (int i = 0; i < N; i++) {
// iに集める
long base = 0;
for (int j = 0; j < N; j++) {
// i -> j -> i
base += dist[i][j] * 2 * T[j];
}
long cost = Long.MAX_VALUE/2;
for (int j = 0; j < N; j++) {
if( T[j] == 0 ) continue;
// i -> j -> i を L -> j -> i に
long a = dist[i][j] * 2;
long b = dist[L][j] + dist[j][i];
cost = Math.min(cost, base-a+b);
}
ans = Math.min(ans, cost);
}
return ans;
}
static long[] calcDist(int i, Edge[][] G) {
long[] dist = new long[N];
Arrays.fill(dist, Integer.MAX_VALUE);
PriorityQueue<State> q = new PriorityQueue<>(Comparator.comparingLong(s -> s.d));
q.add( new State(i, 0) );
dist[i] = 0;
while( !q.isEmpty() ) {
State s = q.poll();
if( dist[s.a] != s.d ) continue;
for (Edge e : G[s.a]) {
int b = e.a == s.a ? e.b : e.a;
long nd = s.d + e.c;
if( dist[b] > nd ) {
dist[b] = nd;
q.add( new State(b, nd) );
}
}
}
return dist;
}
static class State {
int a;
long d;
public State(int a, long d) {
this.a = a;
this.d = d;
}
}
static Edge[][] adjB(int n, Edge[] E) {
Edge[][] adj = new Edge[n][];
int[] cnt = new int[n];
for (Edge e : E) {
cnt[e.a]++;
cnt[e.b]++;
}
for (int i = 0; i < n; i++) {
adj[i] = new Edge[cnt[i]];
}
for (Edge e : E) {
adj[e.a][--cnt[e.a]] = e;
adj[e.b][--cnt[e.b]] = e;
}
return adj;
}
static boolean isAlreadyDone() {
int cnt = 0;
for (int i = 0; i < N; i++) {
if( T[i] > 0 ) {
cnt++;
}
}
return cnt <= 1;
}
@SuppressWarnings("unused")
static class FastScanner {
private BufferedReader reader;
private StringTokenizer tokenizer;
FastScanner(InputStream in) {
reader = new BufferedReader(new InputStreamReader(in));
tokenizer = null;
}
String next() {
if (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
String nextLine() {
if (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
return reader.readLine();
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken("\n");
}
long nextLong() {
return Long.parseLong(next());
}
int nextInt() {
return Integer.parseInt(next());
}
int[] nextIntArray(int n) {
int[] a = new int[n];
for (int i = 0; i < n; i++) a[i] = nextInt();
return a;
}
int[] nextIntArray(int n, int delta) {
int[] a = new int[n];
for (int i = 0; i < n; i++) a[i] = nextInt() + delta;
return a;
}
long[] nextLongArray(int n) {
long[] a = new long[n];
for (int i = 0; i < n; i++) a[i] = nextLong();
return a;
}
}
static void writeLines(int[] as) {
PrintWriter pw = new PrintWriter(System.out);
for (int a : as) pw.println(a);
pw.flush();
}
static void writeLines(long[] as) {
PrintWriter pw = new PrintWriter(System.out);
for (long a : as) pw.println(a);
pw.flush();
}
static void writeSingleLine(int[] as) {
PrintWriter pw = new PrintWriter(System.out);
for (int i = 0; i < as.length; i++) {
if (i != 0) pw.print(" ");
pw.print(as[i]);
}
pw.println();
pw.flush();
}
static int max(int... as) {
int max = Integer.MIN_VALUE;
for (int a : as) max = Math.max(a, max);
return max;
}
static int min(int... as) {
int min = Integer.MAX_VALUE;
for (int a : as) min = Math.min(a, min);
return min;
}
static void debug(Object... args) {
StringJoiner j = new StringJoiner(" ");
for (Object arg : args) {
if (arg == null) j.add("null");
else if (arg instanceof int[]) j.add(Arrays.toString((int[]) arg));
else if (arg instanceof long[]) j.add(Arrays.toString((long[]) arg));
else if (arg instanceof double[]) j.add(Arrays.toString((double[]) arg));
else if (arg instanceof Object[]) j.add(Arrays.toString((Object[]) arg));
else j.add(arg.toString());
}
System.err.println(j.toString());
}
static void printSingleLine(int[] array) {
PrintWriter pw = new PrintWriter(System.out);
for (int i = 0; i < array.length; i++) {
if (i != 0) pw.print(" ");
pw.print(array[i]);
}
pw.println();
pw.flush();
}
static int lowerBound(int[] array, int value) {
int lo = 0, hi = array.length, mid;
while (lo < hi) {
mid = (hi + lo) / 2;
if (array[mid] < value) lo = mid + 1;
else hi = mid;
}
return lo;
}
static int upperBound(int[] array, int value) {
int lo = 0, hi = array.length, mid;
while (lo < hi) {
mid = (hi + lo) / 2;
if (array[mid] <= value) lo = mid + 1;
else hi = mid;
}
return lo;
}
}